Beer Festival
Time limit1sMemory limit256 MB
Given K beers each with a preference and an alcohol level, pick N distinct beers maximizing total preference while minimizing the maximum alcohol level; output that minimum level or -1.
- Level
Medium6 of 10
- Topics
- Binary search, Greedy, Sorting, Heap
- Solved
- No attempts yet
Problem
Starting tomorrow, a beer festival runs in Daegu for N days.
At this festival, K kinds of beer are given out for free.
The festival organizers want more attendees to enjoy a variety of beers. So at the festival, each attendee can receive only one bottle of beer per day, and cannot receive a kind of beer they have received before.
Jeon, a college student who truly loves beer, is thrilled by the news of free beer. He plans to join this beer festival and drink N bottles of beer over the N days.
But Jeon has a serious worry. He loves beer, but he has a condition that makes him faint when he drinks beer with a high alcohol content. If he faints while drinking, he will oversleep and miss his 1st period class the next day, possibly receiving an F.
To solve his problem, Jeon asked Hyun, a genius with a master's degree, and Seung, a genius with a doctorate, to make his liver stronger. But making the liver stronger costs too much, so Jeon planned to strengthen his liver as little as possible.
First, each of the K kinds of beer was assigned a 'preference' and an 'alcohol level'. Preference is a number indicating how much Jeon likes that beer, and alcohol level is a number indicating how strong that beer is. For convenience, Jeon assigned preference and alcohol level as integers.
If the alcohol level of a beer he drinks is higher than Jeon's liver level, his condition triggers, and he faints.
Also, Jeon wants to drink plenty of the beer he likes without triggering his condition. Therefore, he wants the sum of the preferences of the N beers he drinks to be at least M.
Having made such grand plans, Jeon, Hyun, and Seung put their heads together and agonized, then got stressed, abandoned their research, and left to drink beer.
Seeing this, you are going to write a program that, on behalf of the three, outputs the minimum liver level that satisfies the conditions.
Please help the three of them!
Input
The first line gives the duration of the festival N (1 ≤ N ≤ 200,000), the required sum of preferences M (1 ≤ M < 231), and the number of beer kinds that can be drunk K (N ≤ K ≤ 200,000).
The next K lines give, for beers 1 through K, the preference vi (0 ≤ vi ≤ 10,000) and the alcohol level ci (1 ≤ ci < 231) (vi and ci are integers), separated by a space.
All of beers 1 through K are of distinct kinds.
Output
On the first line, output the minimum liver level at which all N beers can be drunk while reaching the given sum of preferences M.
If no matter how much the level is raised the conditions cannot be satisfied, output only "-1" on the first line and nothing further.