Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ALLOW - Allowance

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/allow


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


Được gửi lên bởi:HNUE
Ngày:2009-11-02
Thời gian chạy:0.100s
Giới hạn mã nguồn:1500B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:USACO OCT09

hide comments
2016-09-24 15:40:56
Code:
http://shink.in/Fvl3V
2011-10-04 05:33:34 Mr. Genius
Bài này limit cả source nữa ah`?Bựa thiệt
2009-11-20 14:59:00 gxkrcmk
giải thích đề bài thiếu số 0
"Sau đó trả tiếp 2 đồng 5 xu cho 10 tuần."
2009-11-06 08:50:36 Mệt
Sao lại limt mã nguồn thế? Em làm xong mà ko sub dc.:(
2009-11-03 14:25:51 HNUE
Thực ra để limit 1s thì ko quá khó AC nên hạ xuống 0.5s! :D
Bài này để 0.1s chắc vẫn còn cao ý chứ! :))
2009-11-03 13:25:43 Huy Luu
Em chỉ thấy bài em bựa thôi chứ chẳng tinh tế j` hết hjhj :d

Last edit: 2009-11-03 13:26:55
2009-11-03 05:57:40 AnhDQ
^_^ sao lại limit cả source nữa :p
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.