Atcoder Educational DP Contest D - Knapsack 1

View as PDF
Submit solution
Points: 0.30 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout
Suggester:
NoobCpp
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Có ~N~ đồ vật được đánh số từ ~1~ đến ~N~. Đồ vật thứ ~i~ ~(1 \le i \le N)~ có khối lượng là ~w_i~ và giá trị là ~v_i~.

Taro quyết định chọn một số đồ vật bỏ vào chiếc túi của anh mang về. Sức chứa tối đa của chiếc túi là ~W~, nghĩa là tổng khối lượng các đồ vật có thể mang tối đa là ~W~.

Hãy tìm tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ ~(1 \le N \le 100)~ và ~W~ ~(1 \le W \le 10^5)~: số lượng đồ vật và sức chứa tối đa của chiếc túi.

~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~w_i~ ~(1 \le w_i \le W)~ và ~v_i~ ~(1 \le v_i \le 10^9)~ lần lượt là khối lượng và giá trị của đồ vật thứ ~i~.

Output

Xuất ra tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.

Sample 1

Input
3 8
3 30
4 50
5 60
Output
90

Chọn đồ vật ~1~ và ~3~. Tổng khối lượng sẽ là ~3 + 5 = 8~ và tổng giá trị là ~30 + 60 = 90~.

Sample 2

Input
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
Output
5000000000

Kết quả có thể vượt quá giới hạn kiểu số nguyên ~32~-bit.

Sample 3

Input
6 15
6 5
5 6
6 4
6 6
3 5
7 2
Output
17

Chọn đồ vật ~2~, ~4~ và ~5~. Tổng khối lượng sẽ là ~5 + 6 + 3 = 14~ và tổng giá trị là ~6 + 6 + 5 = 17~.

Comments

Please read the guidelines before commenting.


  • 0
    hahuy0928  commented on Feb. 14, 2025, 2:31 a.m.

    Bài này code python có ac được không vậy?


  • -15
    khiemgia1105  commented on Oct. 4, 2024, 7:48 a.m.

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


  • -13
    cuyu  commented on March 9, 2024, 1:32 a.m. ← edit 3

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


  • -8
    KIET22  commented on Sept. 10, 2023, 4:07 p.m.

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


  • -9
    KIET22  commented on Sept. 7, 2023, 1:22 p.m.

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


  • -4
    teudepdzai  commented on Sept. 4, 2023, 12:44 p.m. ← edited

    .


    • -4
      hieubecclc01  commented on Sept. 9, 2023, 9:13 a.m.

      Bài này bạn nên dùng quy hoạch động cái túi để làm nhé.


  • -61
    dang_phuc_hung  commented on Dec. 30, 2021, 3:18 p.m.

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