Có ~n~ loại đồ vật, mỗi loại có giá ~a[i]~ và số lượng tối đa ~cnt[i]~.

Bạn cần tìm cách mua hàng nhỏ thứ ~K~, trong đó:

• Một cách mua hàng là một bộ ~b[1], b[2], ..., b[n]~, với ~0 \leq b[i] \leq cnt[i]~.
• Tổng chi phí của một cách mua hàng là: ~sum_{i=1}^{n} a[i] \times b[i]~
• Bạn sắp xếp tất cả các cách mua hàng theo chi phí tăng dần và chọn cách có chi phí nhỏ thứ ~K~.

Input

• Dòng đầu chứa hai số nguyên dương ~n, k~ (~n, k \leq 2 \times 10^{5}~).
• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a[i], cnt[i]~ (~a[i] \leq 10^9, cnt[i] \leq 2 \times 10^{5}~).

Output

• In ra chi phí của cách mua hàng nhỏ thứ ~K~.

Scoring

• Subtask 1 (20% số điểm): ~n \leq 20~.
• Subtask 2 (20% số điểm): ~n \leq 100, a[i], b[i] \leq 100~.
• Subtask 3 (20% số điểm): ~cnt[i] = 1~.
• Subtask 4 (40% số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

3 5
2 3
1 2
3 1

Output

3

Note

• Các cách mua hàng hợp lệ có chi phí sắp xếp tăng dần:

  • 0: Không mua gì.
  • 1: Mua 1 món loại 2 (giá 1).
  • 2: Mua 2 món loại 2 (giá 2).
  • 2: Mua 1 món loại 1 (giá 2).
  • 3: Mua 3 món loại 2 (giá 3).
  • 3: Mua 2 món loại 1 (giá 3).
  • 4: Mua 1 món loại 1 và 1 món loại 2 (giá 4).

• Cách mua nhỏ thứ 5 có chi phí 3.