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...