Farmer John sắp hết vật tư và cần mua $H$ $(1 \le H \le 50,000)$ pound cỏ khô cho đàn bò.

Ông biết $N$ $(1 \le N \le 100)$ nhà cung cấp cỏ khô, được đánh số $1,\ldots,N$ để thuận tiện. Nhà cung cấp $i$ bán các gói chứa $P_{i}$ $(1 \le P_{i} \le 5,000)$ pound cỏ khô với giá $C_{i}$ $(1 \le C_{i} \le 5,000)$ đô la. Mỗi nhà cung cấp có số gói không giới hạn, và phải mua nguyên gói.

Hãy giúp FJ tìm chi phí nhỏ nhất cần để mua ít nhất $H$ pound cỏ khô.

Dữ liệu vào

• Dòng 1: hai số nguyên $N$ và $H$, cách nhau bởi một dấu cách.
• Các dòng $2,\ldots,N+1$: dòng $i+1$ chứa hai số nguyên $P_{i}$ và $C_{i}$, cách nhau bởi một dấu cách.

Dữ liệu ra

• Dòng 1: một số nguyên biểu diễn chi phí nhỏ nhất FJ phải trả để có ít nhất $H$ pound cỏ khô.

Ví dụ

Dữ liệu vào 1

2 15
3 2
5 3

Dữ liệu ra 1

9

Ghi chú

FJ có thể mua ba gói từ nhà cung cấp thứ hai với tổng chi phí là 9.

Tác giả bài toán: Neal Wu, 2007