Ngũ cốc là món ăn chính của những chú ngựa đua. Hôm nay, Khôi là người được cử đi mua ngũ cốc tại đại lý NC cho các chú ngựa ăn. Khôi muốn mua X kg ngũ cốc. Ở đại lý NC có N loại ngũ cốc đánh số từ 1 đến N. Loại ngũ cốc thứ i đang có các tải chứa Pi kg với giá Ci mỗi tải. Giả thiết mỗi loại ngũ cốc đều có số lượng không hạn chế và không bán lẻ.

Yêu cầu: Xác định chi phí nhỏ nhất để Khôi có thể mua được ít nhất X kg ngũ cốc.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên N và X (1 ≤ N ≤ 100; 1 ≤ X ≤ 5 ×10^4).

• N dòng tiếp theo, dòng thứ i chứa hai số nguyên Pi, Ci (1 ≤ Pi, Ci ≤ 5000).

Kết quả

• Một số nguyên duy nhất là kết quả bài toán.

Sample Input

3 20
6 4
4 3
1 1

Sample Output

`` 14 ```