Quang đang chơi một trò chơi trên máy tính, trong đó Quang là bên tấn công còn đối phương là bên phòng thủ. Phía đối phương có một bức tường thành gồm \(n\) vị trí, vị trí thứ \(i\) có độ bền là \(a_i\). Đối phương đang lên kế hoạch gia cố lại các vị trí, nhưng những kế hoạch đó đã bị Quang nắm bắt được. Cụ thể, kế hoạch sẽ gồm \(q\) bước, ở bước thứ \(i\) đối phương sẽ gia cố cho các vị trí từ \(l_i\) đến \(r_i\), giúp tăng độ bền của các bức tường ở vị trí này lên \(c_i\). Quang có thể phát động tối đa \(t\) cuộc tấn công có công lực \(w\) nhắm vào một vị trí \(k\) bất kỳ, và cuộc tấn công này sẽ có ảnh hưởng như sau:

• Giảm độ bền ở vị trí \(k\) đi \(w\).
• Giảm độ bền ở vị trí \(k − 1\) và \(k + 1\) đi \(w − 1\).
• …
• Giảm độ bền ở vị trí \(k − w ? + 1\) và \(k + w ? − 1\) đi 1.

Hãy lên kế hoạch giúp Quang giảm sức mạnh của đối thủ về mức thấp nhất có thể. Sức mạnh của đối thủ là độ bền lớn nhất của các vị trí sau khi bị tấn công.

Lưu ý: Độ bền của một vị trí có thể âm.

Input: Nhập từ file ATTACK.inp

• Dòng đầu tiên gồm bốn số nguyên \(n,q,t,w\) (\(1 ≤ n ≤ 4 × 10^5, 0 ≤ q ≤ 4 × 10^5, 0 ≤ t ≤ 1, 1 ≤ w ≤ 10^9\)) – lần lượt là số vị trí của đối thủ, số bước gia cố của đối thủ, số cuộc tấn công tối đa mà Quang có thể phát động và công lực của các cuộc tấn công.
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_i\ (1 ≤ a_i ≤ 2500)\) – độ bền của các vị trí.
• q dòng tiếp theo, mỗi dòng gồm ba só nguyên \(l_i,r_i,c_i\) (\(1 ≤ l_i ≤ r_i ≤ n, 1 ≤ c_i ≤ 2500\)) là các bước gia cố của đối thủ.

Output: Xuất ra file ATTACK.out

• Một dòng duy nhất gồm độ bền lớn nhất của các vị trí sau khi bị tấn công nếu Quang chơi tối ưu.

Scoring

• Subtask 1 (12%): \(t = 0\) và \(n, q ≤ 5000\).
• Subtask 2 (12%): \(t = 0\).
• Subtask 3 (16%): \(t= 1\) và \(n, q ≤ 5000\).
• Subtask 4 (16%): \(t= 1\) và \(n ≤ 5000\).
• Subtask 5 (20%): \(t= 1\) và \(q = 0\).
• Subtask 6 (24%): Không có giới hạn gì thêm.

Example

5 3 0 5
1 2 3 4 5
1 2 3
2 3 4
3 4 5 

12

5 3 1 5
1 2 3 4 5
1 2 3
2 3 4
3 4 5 

7

5 0 1 6
1 2 3 4 5 

-1