Thu gom nước tăng lực (Energy Drink Collector)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ cửa hàng. Cửa hàng $i$ bán tối đa $B_i$ lon nước tăng lực, mỗi lon giá $A_i$. Cần mua đúng $M$ lon. Hãy tìm số tiền ít nhất.

Input

Dòng đầu chứa $N,M$. Mỗi trong $N$ dòng tiếp theo chứa $A_i,B_i$.

Output

In chi phí nhỏ nhất.

Subtask

Các giới hạn chung:

• $1 \le N,M \le 10^5$.

• $1 \le A_i \le 10^9$.

• $1 \le B_i \le 10^5$.

• $\sum B_i \ge M$.

• Subtask 1 (20 điểm): $N,M \le 20$, $A_i \le 100$

• Subtask 2 (30 điểm): $N,M \le 2000$, $A_i \le 10^6$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

2 5
4 9
2 4

Output

12

Giải thích

Mua $4$ lon giá $2$ và $1$ lon giá $4$, tổng $4\cdot2+1\cdot4=12$.