H. Road to Student union
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Egor is qualifying to Student union FCSN. There are $$$n - 1$$$ people in Student union. Egor numbered them from $$$2$$$ to $$$n$$$. Student union chairman Has number $$$n$$$. To get into Student union, Egor must score as much points as possible. $$$i$$$-th Student union member gives $$$a_i$$$ points for completed task. And also some of the Student union members can send Egor to colleagues, so that he can continue to do a job with one of them. So, if Student union member with number $$$k$$$ can direct Egor to colleagues, he calls him two numbers: $$$l_k$$$ and $$$r_k$$$. This means that Yegor can choose any Student union member with number $$$q \in [l_k, r_k]$$$ and go to him. Egor cannot go anywhere without given destination.

Egor marked himself with number $$$1$$$.

Help Egor calculate his chances. Calculate te maximum number of points that Egor can score. If Yegor can't get to the Student union chairman, print "No" (without quotation marks).

Input

The first row contains two integer numbers $$$n$$$ and $$$m$$$ ($$$1 \leq m \lt n \leq 10^5$$$) - the number of Student union members (with due regard for Egor) and number of Student union members, who can send Egor further.

The second row contains integer numbers $$$a_1, a_2, ... , a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) - points, which can score Egor. Note that Yegor already has $$$a[1]$$$ points on the start.

Following $$$m$$$ rows contain 3 integer numbers $$$k$$$, $$$l$$$, $$$r$$$ ($$$1 \leq k \lt l \leq r \leq n$$$) - Student union members description.

Output

Print the maximum number of points that can score Egor, or "No" (without quotation marks), If Yegor can't get to the Student union chairman.

Examples
Input
6 4
5 1 3 3 2 3
1 2 6
3 4 5
2 5 5
5 6 6
Output
13
Input
5 2
6 3 5 1 1
1 3 4
2 4 5
Output
No