Giải bài trực tuyến

Như một phần thưởng cho sản xuất sữa kỷ lục, nông dân John đã quyết định bắt đầu trả

tiền trợ cấp nhỏ cho Bessie hàng tuần.

FJ có một bộ tiền xu tại N (1 ≤ N ≤ 20) mệnh giá khác nhau, trong đó mỗi mệnh giá đồng

xu đều được chia hết bởi mệnh giá lớn tiếp theo.

Sử dụng bộ tiền xu đã cho, FJ muốn trả Bessie một số lượng tiền trợ cấp ít nhất C xu

(1 ≤ C ≤ 100000000) mỗi tuần. Hãy giúp ông ta tính số lượng tuần tối đa mà ông có thể

trả tiền trợ cấp cho Bessie.

Input

-  Dòng 1: Hai số nguyên: N và C

-  Các dòng 2..N+1: Mỗi dòng tương ứng với một loại đồng xu và chứa hai số nguyên:

giá trị V (1 ≤ V ≤ 100000000) của các mệnh giá, và số tiền xu B (1 ≤ B ≤ 1000000) của

mệnh giá này mà Farmer John sở hữu.

Output

-  Một số nguyên là số tuần mà FJ cần trả cho Bessie ít nhất C xu tiền trợ cấp.

Example

Input
3 6
10 1
1 100
5 120

Output:
111


Giải thích output:
FJ có thể trả Bessie với một đồng 10-xu cho 1 tuần.
Sau đó trả tiếp 2 đồng 5 xu cho 10 tuần.
Sau đó trả Bessie 1 đồng 1 xu và 1 đồng 5 xu cho 100 tuần.
 
Translation by Khuong Nguyen Duy
 
Bài này USACO để time limit 1s, mình hạ xuống 0.5s,
để AC các bạn cần có những Solution "tinh tế"! :D