Description

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?

Input Format

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 Format

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

3 2
1 1 1
1 2 1
2 3 1

2

Hint

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