Vương quốc ABC có ~n~ đoạn đường liên tiếp để làm đường đua ngựa, được đánh chỉ số từ ~1~ đến ~n~. Biết rằng, sửa chữa đoạn đường thứ ~i~ tốn chi phí ~c_i~. Có ~m~ cuộc đua ngựa, cuộc đua thứ ~j~ sẽ diễn ra trên các đoạn đường có chỉ số thuộc đoạn ~[l_j, r_j]~. Nếu tất cả các đoạn đường có chỉ số thuộc đoạn ~[l_j, r_j]~ đều được sửa chữa, bạn sẽ thu về lợi nhuận từ tổ chức đua ngựa trên đoạn đường này là ~p_j~. Bạn có thể chọn sửa chữa một số đoạn đường tùy ý sao cho lợi nhuận ròng (được tính bằng tổng lợi nhuận trừ tổng chi phí sửa đường) là lớn nhất.

Input

• Dòng ~1~ chứa hai số nguyên dương ~n, m~ ~(n, m \le 2 \cdot 10^5)~;

• Dòng ~2~ chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~ là chi phí sửa từng đoạn đường ~(0 \le c_i \le 10^9)~;

• ~m~ dòng tiếp theo, dòng thứ ~j~ chứa ~3~ số nguyên dương ~l_j, r_j, p_j~ mô tả cuộc đua ngựa thứ ~j~ ~(l_j \le r_j \le n; p_j \le 10^9)~.

Output

Một số nguyên duy nhất là lợi nhuận ròng lớn nhất đạt được.

Scoring

Sample Input 1

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

Sample Output 1

4

Notes

Chọn sửa các đoạn đường thứ ~1, 2, 3~ và ~7~; chi phí sửa chữa các đoạn đường này là ~3 + 2 + 3 + 3 = 11~.

Tổ chức các cuộc đua thứ ~1, 2~ và ~4~; lợi nhuận thu được là ~5 + 5 + 5 = 15~.

Lợi nhuận ròng thu được: ~15 - 11 = 4~.