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

Street ~i~ starts at intersection ~s_i~ ~(1 \le s_i \le K)~, and ends at a different intersection ~e_i~ ~(1 \le e_i \le K)~, going through no other intersections in between. It takes ~t_i~ ~(1 \le t_i \le 1\,000)~ 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 \le g_i \le 1\,000)~ minutes, then stays red for ~r_i~ ~(1 \le r_i \le 1\,000)~ 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 intersection have traffic lights, so their ~g~ and ~r~ 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 Specification

~2~ integers – ~N~ and ~K~.
The next ~N~ lines contain ~3~ integers each – ~s_i~, ~e_i~, and ~t_i~.
The next ~K~ lines contain ~2~ integers each – ~g_i~, and ~r_i~.

Output Specification

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.

Sample 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

Sample Output

19

Explanation

The city looks something like this (Jim-Bob's best route is shown in red):

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 as intersections ~2~ and ~5~ just in time, as they turn red ~1~ minute after he passes.