Gửi bài giải


Điểm: 0,92 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
USACO October 2009
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.