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 contains 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 additional 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