ALLOW - Allowance
Giới hạn- Thời gian: 0.1s
- Bộ nhớ: 1536MB
- Mã nguồn: 1500 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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
- Người up: hnue
- Nguồn bài: USACO OCT09