KFC cần mua ~M~ đùi gà từ ~N~ nhà cung cấp. Nhà cung cấp thứ ~i~ có thể bán tối đa ~a_i~ đùi gà, mỗi đùi gà giá ~b_i~. Dữ liệu đảm bảo luôn mua đủ ~M~ đùi gà.

Yêu cầu

Tính số tiền ít nhất cần trả.

Input

Dòng đầu chứa hai số nguyên ~N,M~ ~(1 \le N \le 10^5, 1 \le M \le 10^9)~.

~N~ dòng tiếp theo, mỗi dòng chứa hai số ~a_i,b_i~ ~(1 \le a_i,b_i \le 10^9)~.

Output

In ra tổng số tiền ít nhất.

Subtask

• 50% số điểm: ~N \le 10^3~.
• 50% số điểm: ~N \le 10^5~.

Ví dụ

3 10
5 10
5 15
6 5

70