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 Codeforces (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 Codeforces. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên Codeforces

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