Hide

Problem D
DJ Gigs

/problems/djgigs/file/statement/en/img-0001.jpg
Photo by Zierros

Doug James is an up-and-coming DJ from Graphland who’s had a tough time making it big. This all changed with the release of his latest EP Wiggly Waves, which is the first album in history to go both Platinum and Uranium. With his newfound popularity, Doug (a.k.a. DJ Polygon) needs help with a problem most artists would be lucky to face: deciding which of his many gig offers to take.

There are K venues in Graphland, connected by R roads. The venues are numbered 1 to K. Doug’s house is venue 1, and he is ready to leave or perform at time t=0.

Doug has G gig offers. The i-th gig is at venue Vi, runs during the time interval [Si,Ei) (inclusive start, exclusive end), and pays out Mi cryptocents. Doug can’t take multiple gigs at the same time, and he can’t take gigs while he’s traveling between venues.

Doug is overwhelmed by his newfound fame and many gig requests, and wants your help making as much money as possible.

Input

The first line of the input contains three integers G, K, and R: the number of gigs Doug has been offered, the number of venues in Graphland, and the number of roads connecting these venues.

These integers satisfy 1G200000, 1K100, and 0Rmin(4000,K(K1)/2).

Then follow R lines, each of which has three integers Ai, Bi, and Ti, specifying the i-th (bidirectional) road. The i-th road connects venues Ai and Bi and it takes time Ti to travel the road in either direction. The values satisfy 1Ai,BiK, AiBi, and 1Ti1000000. Every road has two distinct endpoints, and there is at most one road between any pair of venues.

Then follow G lines, each of which has four integers Vi, Si, Ei, and Mi. This means the i-th gig runs from time Si (inclusive) to Ei (exclusive) at venue Vi, and pays Mi cryptocents. These values satisfy the bounds 0Si<Ei1000000000 and 1Mi1000000.

Output

Output a single integer: the maximum number of cryptocents that DJ Polygon can make by taking on the right gigs.

Sample Explanation

In the first sample, There are two gigs at venue 1 and one gig at venue 2. Doug can either play both gigs at venue 1 for 11 cryptocents, or spend the first 10 units of time traveling to venue 2 and play that gig for 33 cryptocents. He chooses the latter.

In the second sample, Doug makes the most by staying at venue 1 and playing both of those gigs to earn 70 cryptocents.

Sample Input 1 Sample Output 1
3 2 1
1 2 10
1 4 6 6
1 6 10 5
2 10 30 33
33
Sample Input 2 Sample Output 2
3 2 1
1 2 10
1 4 6 30
1 6 10 40
2 10 30 50
70
Hide

Please log in to submit a solution to this problem

Log in