Tổ chức giải đua

Có $n$ đoạn đường nối tiếp nhau, đánh số từ $1$ đến $n$ theo thứ tự từ trái sang phải. Đoạn đường thứ $i$ đang hư hỏng và cần chi $a_i$ đồng để sửa chữa.

Có $m$ giải đua xe có thể được tổ chức. Giải đua thứ $j$ sử dụng toàn bộ các đoạn đường từ $l{b}_j$ đến $u{b}_j$, và nếu được tổ chức thì bạn thu về $p_j$ đồng. Một giải đua chỉ có thể diễn ra khi tất cả các đoạn đường mà nó sử dụng đều đã được sửa. Các giải đua diễn ra vào những thời điểm khác nhau nên một đoạn đường có thể phục vụ nhiều giải đua cùng lúc.

Bạn được tự do chọn tập các đoạn đường để sửa (có thể sửa tất cả, hoặc không sửa đoạn nào). Sau khi chọn xong, mọi giải đua có đủ điều kiện đều được tổ chức. Lợi nhuận của bạn bằng tổng tiền thu được từ các giải đua đã tổ chức trừ đi tổng chi phí sửa đường.

Hãy tìm lợi nhuận lớn nhất có thể đạt được. Vì luôn có thể không sửa đoạn đường nào để nhận lợi nhuận $0$, đáp án không bao giờ âm.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số đoạn đường và số giải đua.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa một số nguyên $a_i$: chi phí sửa đoạn đường thứ $i$.
• $m$ dòng cuối, dòng thứ $j$ chứa ba số nguyên $l{b}_j$, $u{b}_j$, $p_j$: giải đua thứ $j$ dùng các đoạn đường từ $l{b}_j$ đến $u{b}_j$ và mang lại $p_j$ đồng.

Dữ liệu ra

Một số nguyên duy nhất là lợi nhuận lớn nhất.

Ràng buộc

• $1\le n,m\le 2·{10}^5$
• $0\le a_i\le {10}^9$
• $1\le l{b}_j\le u{b}_j\le n$
• $1\le p_j\le {10}^9$

Đáp án có thể vượt quá phạm vi số nguyên 32 bit.

Ví dụ