yyq and his friends, a total of $n$ people (numbered 1 to $n$, with yyq numbered 1), go to a restaurant for "Crazy Thursday". The $i$-th person initially has $a_i$ yuan of pocket money, meaning the total expenditure of the $i$-th person cannot exceed $a_i$ yuan. Since the distance to the restaurant varies for each person, the taxi fare for the $i$-th person is $V_i$ yuan.

yyq and his friends ordered a total of $m$ dishes. For the $i$-th dish, which has a value of $W_i$ yuan, it is consumed by the $x_i$-th person and the $y_i$-th person. When paying the bill, $x_i$ and $y_i$ can decide for themselves how much each of them pays (the amount paid by these two people for this dish must be a non-negative integer, and the sum of the payments by $x_i$ and $y_i$ must be $W_i$ yuan). Since today is yyq's birthday, yyq wants his total expenditure (the sum of his taxi fare and the cost of the dishes he pays for) to be the maximum, meaning it must be strictly greater than the total expenditure of any other person.

Can yyq's wish be fulfilled without anyone exceeding their budget?

Note: $x_i$ and $y_i$ may be equal, which means one person eats the dish alone and pays for it entirely.

Input

The first line contains two integers $n, m$ ($2 \le n \le 10^3, 1 \le m \le 10^3$), representing the number of people and the number of dishes, respectively.

The next $n$ lines each contain two integers $a_i, V_i$ ($1 \le V_i \le a_i \le 10^6$), representing the pocket money and taxi fare for each of the $n$ people.

The next $m$ lines each contain three integers $x_i, y_i, W_i$ ($1 \le x_i, y_i \le n, 1 \le W_i \le 10^6$), representing the information for the $m$ dishes: the $i$-th dish has a value of $W_i$ yuan and is consumed and paid for by $x_i$ and $y_i$. (Note that $x_i$ and $y_i$ may be equal.)

Output

A single line. If yyq can fulfill his wish, output YES, otherwise output NO.

Examples

Input 1

3 3
10 5
6 5
15 1
1 2 3
1 3 1
2 3 2

Output 1

YES

Input 2

2 1
1 1
1 1
1 2 1

Output 2

NO

Note

For the first example, one possible scenario is: for the first dish, yyq pays 3 yuan; for the second dish, yyq pays 1 yuan; for the third dish, person 2 and person 3 each pay 1 yuan. Ultimately, yyq's total expenditure is $5 + 3 + 1 = 9$ yuan, person 2's total expenditure is $5 + 1 = 6$ yuan, and person 3's total expenditure is $1 + 1 = 2$ yuan. yyq's wish is fulfilled.

For the second example, no matter who pays, someone will exceed their budget, so yyq cannot fulfill his wish.