Traffic Lights

Jim-Bob lives in a strange city where the streets don't necessarily run NS or EW. Instead the N (1 ≤ N ≤ 100,000) streets run seemingly at random, sometimes crossing over each other by bridges, and intersecting with one another at exactly K (1 ≤ K ≤ 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 ≤ s_i ≤ K), and ends at a different intersection e_i (1 ≤ e_i ≤ K), going through no other intersections in between. It takes t_i (1 ≤ t_i ≤ 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 ≤ g_i ≤ 1,000) minutes, then stays red for r_i (1 ≤ r_i ≤ 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

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

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.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 17, 2008
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

g_1, g_n, r_1, r_n are nonzero.

Fixed

This is a graph theory problem that's just asking for the shortest path between 2 nodes, made trickier by the presence of traffic lights.

The algorithm to use here is called "Dijkstra's", so you can try looking that up and coding it. We'll teach this eventually in class though.