Allowance


Submit solution

Points: 0.92 (partial)
Time limit: 0.375s
Memory limit: 512M

Problem type

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 \leq N \leq 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 \leq C \leq 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 \leq V \leq 100000000)\) của các mệnh giá, và số tiền xu \(B\) \((1 \leq B \leq 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.

Sample Input

3 6
10 1
1 100
5 120

Sample Output

111

Note

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


Comments

There are no comments at the moment.