Problem D
DJ Gigs
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
Doug has
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
These integers satisfy
Then follow
Then follow
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
In the second sample, Doug makes the most by staying at
venue
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 |