A Greedy Problem

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

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

Input Specification

First line 2 integers, N and M.

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

Output Specification

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

Subtasks

For all subtasks:

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

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

0 \le p_i \le 1\,000

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

Subtask 1 [20%]

1 \le N \le 100

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

Subtask 2 [80%]

No further constraints.

Sample Input

5 100
5 20
9 40
3 10
8 80
6 30

Sample Output

630

Sample Explanation

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

Comments

There are no comments at the moment.