BITCOIN
Xem dạng PDF
Gửi bài giải
Điểm:
2,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Nam đang nghiên cứu thị trường tiền ảo, Nam quan tâm đến đồng bitcoin và dự báo sau ~n~ ngày thị trường bitcoin sẽ có một cú biến động cực lớn, hơn thế nữa Nam còn biết trong ~n~ ngày tới, buổi sáng ngày thứ ~i~ ~(i = 1, \ldots, n)~, sẽ có người bán ~b_i~ bitcoin với tổng số tiền là ~a_i~ đô la. Nam quyết định đi làm thêm để kiếm tiền mua bitcoin chờ lên giá, cuối mỗi ngày Nam sẽ nhận được ~x~ đô la nhờ vào việc làm thêm của mình.
Yêu cầu
Lập trình tính số bitcoin nhiều nhất Nam có thể mua trước cơn bùng nổ giá.
Dữ liệu
- Dòng đầu tiên gồm hai số nguyên dương ~n, x~ ~(n \le 100; x \le 10^8)~ là thời gian đếm ngược thị trường bitcoin bùng nổ và số tiền lương Nam nhận được sau mỗi ngày.
- ~n~ dòng sau, dòng thứ ~i~ chứa ~2~ số nguyên không âm ~a_i~ và ~b_i~ ~(i = 1 \ldots n)~, lần lượt ~a_i~ là số tiền để mua hết ~b_i~ bitcoin.
Kết quả
- Số bitcoin lớn nhất Nam có thể mua.
Ràng buộc
| Subtask | Điểm | Ràng buộc thêm |
|---|---|---|
| 1 | 40% | ~x \le 10^8~, ~a_i \le 1~, ~b_i \le 5 \cdot 10^3~, ~n \le 100~ |
| 2 | 30% | ~x \le 10^8~, ~a_i \le 10^4~, ~b_i \le 10^3~, ~n \le 100~, tất cả số lượng bitcoin mua được ở ngày sau sẽ ít hơn ngày trước và các giá trị ~a_i~ là bằng nhau |
| 3 | 30% | ~x \le 10^8~, ~a_i \le 10^4~, ~b_i \le 10^3~, ~n \le 100~ |
Ví dụ
Ví dụ 1
Input
1 101
1 100
Output
0
Giải thích. Vì cuối ngày Nam mới nhận được lương nên không thể mua được bất kì bitcoin nào.
Ví dụ 2
Input
5 2
2 1
1 2
3 5
3 2
3 2
Output
9
Giải thích.
- Hết ngày ~1~ kiếm được ~2~ đô la;
- Ngày ~2~: mua ~2~ bitcoin với giá ~1~ đô la, còn ~1~ đô la;
- Hết ngày ~2~ kiếm được ~2~ đô la, tổng có ~3~ đô la;
- Ngày thứ ~3~: mua ~5~ bitcoin với giá ~3~ đô la;
- Hết ngày ~3~ kiếm được ~2~ đô la;
- Hết ngày ~4~ kiếm được ~2~ đô la, nên có ~4~ đô la;
- Ngày cuối cùng mua ~2~ bitcoin với giá ~3~ đô la;
- Tổng cộng Nam mua được ~9~ bitcoin.
Đang tải...