Allowance

View as PDF

Submit solution

Points: 0.92 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
USACO October 2009
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Như một phần thưởng cho khả năng sản xuất sữa kỷ lục, Farmer John đã quyết định bắt đầu trả tiền trợ cấp nhỏ cho Bessie hàng tuần.

Farmer John 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, Farmer John 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à Farmer John 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: Farmer John 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

Please read the guidelines before commenting.


There are no comments at the moment.