An quyết định mua \(M\) lon nước tăng lực.

Có \(N\) cửa hàng bán nước tăng lực. Ở cửa hàng thứ \(i\), anh ta có thể mua nhiều nhất \(B_i\) lon nước tăng lực với giá \(A_i\) yên (đơn vị tiền tệ của Nhật Bản) mỗi lon.

Số tiền tối thiểu mà anh ta cần để mua \(M\) lon nước tăng lực là bao nhiêu?

Đầu vào đảm bảo rằng, với số tiền đủ, luôn có thể mua được \(M\) lon nước tăng lực.

Ràng buộc

• Tất cả giá trị đầu vào là số nguyên.
• \(1 \leq N, M \leq 10^5\)
• \(1 \leq A_i \leq 10^9\)
• \(1 \leq B_i \leq 10^5\)
• \(B_1 + B_2 + ... + B_N \geq M\)

INPUT FORMAT

• Đầu vào được cung cấp từ Standard Input theo định dạng sau:

  N M
  A_1 B_1
  A_2 B_2
  ...
  A_N B_N

OUTPUT FORMAT

• In ra số tiền tối thiểu mà An cần để mua \(M\) lon nước tăng lực.

Ví dụ:

Input

2 5
4 9
2 4

Output

12

Với 12 yên, chúng ta có thể mua một lon tại cửa hàng thứ nhất và bốn lon tại cửa hàng thứ hai, tổng cộng là năm lon. Tuy nhiên, chúng ta không thể mua năm lon với 11 yên hoặc ít hơn.

Input

4 30
6 18
2 5
3 10
7 9

Output

130

Giải thích ví dụ mẫu

Ví dụ 1:

• Input: 2 5, 4 9, 2 4
• Giải thích: Mua 1 lon ở cửa hàng thứ nhất và 4 lon ở cửa hàng thứ hai, tổng chi phí là 12 yên.

Ví dụ 2:

• Input: 4 30, 6 18, 2 5, 3 10, 7 9
• Giải thích: Cần 130 yên để mua 30 lon bằng cách kết hợp các cửa hàng khác nhau.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House