Edgar Dijkstra was bored of inventing new algorithms, so he went out of town for a short morning drive to brighten his mood. Suddenly, a figure smashed down his car window as he started driving out of the driveway. Oh my goodness, it's the zombie apocalypse!
Edgar Dijkstra had spent his entire life in discrete mathematics, and had not watched a single episode of The Walking Dead! How could he survive the zombie apocalypse? Panicked, he slammed his gears into reverse and sped out of his driveway onto the road, INTO A HORDE OF WALKERS!
He knew his house was a fortified bunker, and everyone within his house would be safe from the zombies. However, the self-sacrifical Edgar Dijkstra wants to head out selflessly to save his family and friends! His town can be represented by a series of nodes and edges where the nodes represent the road intersections and the edges represent the roads in the town.
There are a total of N road intersections and E roads connecting them. Each road intersection is numbered from 0 to N-1 and each road is numbered from 0 to E-1. Edgar Dijkstra's bunker is located at node 0. Each road i in the town connects road intersections Ai and Bi and takes Ti time to traverse. Edgar Dijkstra also has K family members he wants to save, with family member i located at intersection Li and has to be saved latest by time Si or they will be brutally eaten by zombies.
To save a family member, Edgar Dijkstra has to travel from his fortified bunker house to the road intersection that the family member is at, and bring the family member back to the bunker. He can only pick up one family member at a time due to his small car capacity.
Help Edgar Dijkstra calculate what is the maximum number of family members he can save.
The first line of input will contain three integers, N
The next E
lines of input will contain three integers each, with the i
th line containing Ai
The next K
lines of input will contain two integers each, with the i
th line containing Li
Your output should contain one line with one integer, stating the maximum number of family members Edgar Dijkstra can save.
For all subtasks: 0 ≤ K ≤ N.
Subtask 1 (8%): 0 ≤ N, E, K ≤ 8.
Subtask 2 (14%): 0 ≤ N, E ≤ 100. 0 ≤ K ≤ 13.
Subtask 3 (20%): 0 ≤ N, E, K ≤ 100.
Subtask 4 (23%): 0 ≤ N, E, K ≤ 1000.
Subtask 5 (35%): 0 ≤ N, E ≤ 100 000.
7 8 3
0 1 3
0 2 1
1 3 2
2 3 1
1 4 2
3 4 2
3 5 3
3 6 1