A Greedy Problem

View as PDF

Submit solution

All submissions

Best submissions

Points: 5 (partial)

Time limit: 1.0s

Memory limit: 64M

Problem type

You are given $N$ ~N~ factories and $M$ ~M~ total number of boxes which you must fulfill. Each factory has 2 values, $p_i$ ~p_i~ and $a_i$ ~a_i~, denoting the price in cents that factory $i$ ~i~ charges for one box, and the total number of boxes factory $i$ ~i~ has respectively.

Please find the minimum price in cents in order to obtain at least $M$ ~M~ boxes. It is guaranteed that at least $M$ ~M~ boxes can be achieved.

Input Specification

First line contains 2 integers, $N$ ~N~ and $M$ ~M~.

Next $N$ ~N~ lines each contain 2 integers, $p_i$ ~p_i~ and $a_i$ ~a_i~.

Output Specification

Output the minimum price in cents in order to obtain at least $M$ ~M~ boxes.

Subtasks

For all subtasks:

$1 \le N \le 2 \times 10^5$ ~1 \le N \le 2 \times 10^5~

$1 \le M \le 2 \times 10^9$ ~1 \le M \le 2 \times 10^9~

$0 \le p_i \le 1\,000$ ~0 \le p_i \le 1\,000~

$0 \le a_i \le 2 \times 10^6$ ~0 \le a_i \le 2 \times 10^6~

Subtask 1 [20%]

$1 \le N \le 100$ ~1 \le N \le 100~

$1 \le M \le 5 \times 10^7$ ~1 \le M \le 5 \times 10^7~

Subtask 2 [80%]

No additional constraints.

Sample Input

Sample Output

Sample Explanation

Price per Box	Units available	Units bought	Prices $\times$ ~\times~ # of units	Total Cost	Notes
$5$ ~5~	$20$ ~20~	$20$ ~20~	$5 \times 20$ ~5 \times 20~	$100$ ~100~
$9$ ~9~	$40$ ~40~	$0$ ~0~			Bought no boxes from factory 2
$3$ ~3~	$10$ ~10~	$10$ ~10~	$3 \times 10$ ~3 \times 10~	$30$ ~30~
$8$ ~8~	$80$ ~80~	$40$ ~40~	$8 \times 40$ ~8 \times 40~	$320$ ~320~	Did not buy all 80 units
$6$ ~6~	$30$ ~30~	$30$ ~30~	$6 \times 30$ ~6 \times 30~	$180$ ~180~
Total	$180$ ~180~	$100$ ~100~		$630$ ~630~	Cheapest total cost

Comments

1

pto1026 commented on Nov. 12, 2021, 4:07 p.m.

Can anyone look at my code and tell me where I have gone wrong, or point out a test case that will highlight my missteps.

2

Nils_Emmenegger commented on Nov. 12, 2021, 4:20 p.m. ← edited →

Since $M$ ~M~ can get pretty large (up to $2 \times 10^9$ ~2 \times 10^9~), simulating the purchase of every box individually will be too slow.