Butcher Shop
Time limit2sMemory limit128 MB
Given N meat pieces with weight and price, find the minimum cost so that buying one piece and receiving all strictly cheaper pieces free reaches a target total weight M.
- Level
Medium6 of 10
- Topics
- Sorting, Prefix sum, Greedy
- Solved
- No attempts yet
Problem
Eunhye wants to buy meat at a butcher shop. At an ordinary shop, she could ask for exactly the amount she wants, but this shop is holding a sale and sells only N pieces of meat that have already been cut.
Each piece has a fixed weight and price. If she buys a piece, she may receive any pieces whose prices are lower than that piece's price for free. Pieces with the same price are not cheaper, so each such piece must be bought separately if she needs it. Because the pieces may be from different cuts, price and weight are not necessarily proportional.
Eunhye only cares about obtaining at least the total amount of meat she needs, regardless of cut. If it costs less, she may obtain more meat than necessary. Given the information for all pieces, find the minimum amount of money she must pay to obtain at least the required amount.
Input
The first line contains two integers N (1 ≤ N ≤ 100,000) and M (1 ≤ M ≤ 2,147,483,647). N is the number of meat pieces, and M is the amount of meat Eunhye needs.
Each of the next N lines contains two nonnegative integers: the weight and price of one piece of meat. The sum of all weights and the sum of all prices are each at most 2,147,483,647.
Output
Print the minimum required cost on the first line. If it is impossible to obtain the required amount, print -1.
Hint
If she buys the piece with weight 4 and price 8, she can receive all cheaper pieces for free. The total weight obtained is then 10kg, which is at least the required 9kg.