Tèo có một hàng rào gồm \(n\) thanh gỗ. Ban đầu mỗi thanh có độ dài \(a_i\). Chú thợ sơn thực hiện \(q\) lần: mỗi lần sơn lên các thanh từ \(l\) đến \(r\), làm thanh gỗ dày thêm \(k\) cm.

Sau \(q\) lần sơn, Tèo muốn biết độ dài của thanh gỗ dày nhất.

Gợi ý: Dùng difference array để cập nhật các đoạn, sau đó tìm max trên mảng kết quả.

Input

Dòng đầu chứa \(n\) và \(q\) (\(1 \le n, q \le 10^5\)). Dòng hai chứa \(n\) số \(a_i\) (\(1 \le a_i \le 10^9\)). \(q\) dòng tiếp theo, mỗi dòng chứa \(l, r, k\) (\(1 \le l \le r \le n\), \(1 \le k \le 10^9\)).

Output

In ra độ dài lớn nhất sau khi sơn.

Example

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

Output:

20