Jim-Bob lives in a strange city where the streets don’t necessarily run NS or EW. Instead, the $N$ ($1 \leq N \leq 10^5$) streets run seemingly at random, sometimes crossing over each other by bridges, and intersecting with one another at exactly $K$ ($1 \leq K \leq 1000$) intersections. Each intersection consists of some streets coming together, as well as a traffic light.

Street $i$ starts at intersection $s_i$ ($1 \leq s_i \leq K$), and ends at a different intersection $e_i$ ($1 \leq e_i \leq K$), going through no other intersections in between. It takes $t_i$ ($1 \leq t_i \leq 1000$) minutes to travel down street $i$ (this number is derived from the length, the average pothole size, and the amount of roadkill). Each road can be travelled in either direction in the same amount of time.

The traffic lights in this city are also strange. First of all, each one only alternates between green and red. Each light also cycles through these colours at a different rate – the traffic light located at intersection $i$ stays green for $g_i$ ($1 \leq g_i \leq 1000$) minutes, then stays red for $r_i$ ($1 \leq r_i \leq 1000$) minutes, then goes back to green, and so on.

Jim-Bob always obeys the law, and will never run a red light. If he arrives at an intersection while the light is green, he can pass right through it. Otherwise, he must wait there until the light turns green. If he gets to an intersection just as the traffic light is turning red, he must wait. It takes no time to drive through an intersection, so the light will never turn red on him as he drives through.

Jim-Bob starts at his house, also known as intersection $1$. As soon as he leaves his house, all the traffic lights turn green, starting their green-red-green cycle. He wishes to drive to Billy-Bob’s house (which is right at intersection $K$) as fast as possible. Neither the starting nor the finishing intersections have traffic lights, so their $g$ and $r$ values will be given as 0. Find the minimum number of minutes Jim-Bob can take to drive from his house to Billy-Bob’s.

Input

Line $1$: 2 integers, $N$ and $K$

Next $N$ lines: 3 integers, $s_i$, $e_i$, and $t_i$, for $i=1..N$

Next $K$ lines: 2 integers, $g_i$ and $r_i$, for $i=1..K$

Output

A single integer – the minimum number of minutes it takes to drive from Jim-Bob’s house to Billy-Bob’s. It will always be possible to do this.

Example

Input:

7 6
1 2 4
1 3 1
3 5 2
2 4 2
2 5 6
5 4 2
5 6 10
0 0
5 5
1 20
2 5
10 2
0 0

Output:

19

Explanation of Sample:

Jim-Bob can drive to intersection 2 (4 min), drive on to intersection 4 (2 min), wait for the green light (1 min), drive down to intersection 5 (2 min), and finally drive to Billy-Bob’s house (10 min). This is a total of 19 minutes.

Note: The traffic light at intersection 3 only stays green for 1 minute, which means that Jim-Bob would just miss it if he drove directly there. On the other hand, he makes the green lights at intersections 2 and 5 just in time, as they turn red 1 minute after he passes.