P2367 Chinese Scores

The Chinese exam has ended, and the scores are, as always, problematic.

The Chinese teacher always writes scores wrong, so when she corrects them, she gets exhausted. She keeps adding points again and again to certain students, and she also needs to keep track of the minimum score. Can you help her?

The first line has two integers $n$, $p$, representing the number of students and the number of additions. The second line has $n$ numbers, $a_1 \sim a_n$, representing each student's initial score. The next $p$ lines each have three numbers, $x$, $y$, $z$, representing adding $z$ points to each student from the $x$-th to the $y$-th, inclusive.

Output only one line, representing the class minimum score after the changes.

For $40\%$ of the testdata, $n \le 10^3$. For $60\%$ of the testdata, $n \le 10^4$. For $80\%$ of the testdata, $n \le 10^5$. For $100\%$ of the testdata, $n \le 5\times 10^6$, $p \le n$, initial scores $\le 100$, $z \le 100$. Translated by ChatGPT 5