Chocolate Buying

View as PDF

Submit solution


Points: 0.14 (partial)
Time limit: 0.38s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
USACO February 2010 - Silver Division
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Những con bò rất thích ăn Sô-cô-la, nên Farmer John quyết định mua một ít cho chúng.

Cửa hàng có ~N~ loại sô-cô-la (được đánh số từ ~1 \dots N~) với số lượng mỗi loại không hạn chế. Loại thứ ~i~ có giá ~P_i~ tiền và có đúng ~C_i~ con bò muốn ăn loại Sô-cô-la ấy. Farmer John có ~B~ tiền để mua Sô-cô-la cho lũ bò.

Hỏi số bò tối đa mà Farmer John có thể phục vụ là bao nhiêu? Biết rằng mỗi con bò chỉ thích một loại sô-cô-la, và nó chỉ được ăn loại sô-cô-la ấy.

Input

Dòng đầu tiên là hai số nguyên ~N~ và ~B~.

~N~ dòng tiếp theo, dòng thứ ~i + 1~ là hai số nguyên dương ~P_i~ và ~C_i~.

Output

Gồm một số duy nhất là kết quả.

Giới hạn

  • ~1 \le N \le 10^{5}~
  • ~1 \le B \le 10^{18}~
  • ~1 \le C_i \le 10^{18}~
  • ~1 \le P_i \le 10^{18}~

Sample Input

5 50
5 3
1 1
10 4
7 2
60 1

Sample Output

8

Note

Farmer John sẽ mua như sau:

  • Mua ~3~ gói sô-cô-la loại ~1~ mất ~3 \times 5 = 15\$~.
  • Mua ~1~ gói sô-cô-la loại ~2~ mất ~1 \times 1 = 1\$~.
  • Mua ~2~ gói sô-cô-la loại ~3~ mất ~2 \times 10 = 20\$~.
  • Mua ~2~ gói sô-cô-la loại ~4~ mất ~2 \times 7 = 14\$~.

Comments

Please read the guidelines before commenting.



  • -6
    Star_PhongMinh_Pham_6I0  commented on Oct. 13, 2022, 11:33 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -4
    Star_PhongMinh_Pham_6I0  commented on Oct. 13, 2022, 11:26 a.m.

    hellhell


  • -1
    star_TheHung_Ngo  commented on Oct. 13, 2022, 11:25 a.m.

    h e l o l


  • -4
    vuducdung9113  commented on March 29, 2022, 10:10 a.m.

    xin chao` moi nguoi


  • -5
    ___  commented on March 15, 2022, 10:53 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.