Cái túi 1

View as PDF
Submit solution
Points: 0.42 (partial)
Time limit: 0.9s
Memory limit: 512M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cây khế nhà Khánh rất sai quả nên có một con chim to to đến ăn. Ăn xong, chim chở Khánh ra đảo để trả công bằng vàng. Đảo có ~N~ cục vàng. Anh ấy muốn chuyển hết cả ~N~ cục vàng của mình về nhà. Nhưng khổ nổi các cục vàng này lại có trọng lượng và kích thước khổng lồ. Khánh đem theo một cái túi ba trăm gang to đùng nhưng vẫn chưa chắc chứa hết đống vàng này. Khổ quá đi! Lấy cục nào, bỏ cục nào bây giờ! Các bạn giúp anh ấy tìm ra một cách chọn vàng để thu được giá trị lớn nhất mà vẫn không làm rách túi đi.

Input

  • Dòng ~1~: Chứa ~2~ số nguyên: số cục vàng ~N~ ~\left(1 \leq N \leq 40\right)~ và tải trọng tối đa của túi ~M~ ~\left(1 \leq M \leq 10^9\right)~.
  • ~N~ dòng sau: Mỗi dòng chứa ~2~ số nguyên: trọng lượng ~W_{i}~ và giá trị ~V_{i}~ của cục vàng thứ ~i~ ~\left(1 \leq W_{i}, V_{i} \leq 10^8\right)~.

Output

  • Một số nguyên duy nhất là giá trị lớn nhất thu được.

Sample Input

3 4
1 4
2 5
3 6

Sample Output

10

Comments

Please read the guidelines before commenting.


  • 0
    hmtphong7749  commented on Feb. 14, 2025, 1:58 p.m.

    sao cứ đúng được 9 đầu xong lại sai nhỉ


  • 0
    mickey21082013  commented on Dec. 7, 2024, 2:27 p.m.

    hi hi


  • 2
    phancuongtmtlhp  commented on Nov. 20, 2024, 5:12 a.m.

    Ai đó cho mình xin ý tưởng bài này vs! em đọc sol mà không có hiểu


  • -4
    tienthinh081  commented on Aug. 31, 2024, 1:29 a.m.

    mik bị lỗi runtime là sao ạ


  • 0
    dongquan247  commented on Aug. 7, 2024, 10:55 p.m. ← edited

    bị sai test case cuối :(


  • -23
    TBThao  commented on Nov. 23, 2023, 5:33 a.m.

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


  • 58
    I_love_Hoang_Yen  commented on Aug. 20, 2021, 3:32 a.m. ← edited

    Mình vừa cập nhật bộ test bài này và rejudge (cảm ơn bạn kazamahoang đã đóng góp test). 1 số bạn đã mất AC.

    Ngoài ra bộ test bài này không phù hợp để chấm kiểu OI, nên mình đã đổi sang chấm kiểu ICPC.