Nam biết rằng trong mùa mưa lũ thì khả năng mất điện thường xuyên là rất lớn. Vì vậy anh ấy muốn mua ~M~ cục pin dự phòng cho mùa học đội tuyển. Có ~N~ cửa hàng bán các cục pin dự phòng. Ở cửa hàng thứ ~i~, anh ta có thể mua nhiều nhất ~B_i~ pin dự phòng với giá ~A_i~ đồng mỗi cục.

Yêu cầu

Hãy tính số tiền tối thiểu mà Nam có thể mua được ~M~ cục pin dự phòng. Đảm bảo rằng luôn có một số tiền đủ lớn để có thể mua được ~M~ cục pin.

Input

Dòng đầu tiên chứa 2 số nguyên ~N~ và ~M~ – tương ứng với số cửa hàng và số cục pin dự phòng Nam muốn mua.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa giá trị ~A_i~ và ~B_i~ tương ứng với giá trị của mỗi cục pin.

Output

Số tiền tối thiểu mà Nam có thể mua ~M~ cục pin dự phòng.

Ràng buộc

• ~1 \leq N, M \leq 10^5~; ~1 \leq A_i \leq 10^9~; ~1 \leq B_i \leq 10^5~; ~B_1 + \cdots + B_N \geq M~
• Tất cả các giá trị trong đầu vào là số nguyên, các số cách nhau 1 khoảng trắng.

Sample Test

Input

2 5
4 9
2 4

Output

12

Giải thích

Với ~12~ đồng, Nam có thể mua ~1~ cục pin ở cửa hàng đầu tiên và ~4~ cục pin ở cửa hàng thứ hai, tổng cộng là ~5~ cục pin.