Ba lô 0/1 chuẩn

Bối cảnh và bài toán

Có n linh kiện, mỗi linh kiện có trọng lượng w và giá trị v. Mỗi linh kiện chọn tối đa một lần, tổng trọng lượng không vượt W.

Yêu cầu

Tìm tổng giá trị lớn nhất.

Input

Dòng 1 n W; n dòng w_i v_i.

Output

In giá trị lớn nhất.

Ràng buộc

• 1 <= n <= 100
• 1 <= W <= 10^5
• 1 <= w_i <= W
• 1 <= v_i <= 10^9

Chấm điểm

Ví dụ 1

Input

3 8
3 30
4 50
5 60

Output

90

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

2 3
4 100
2 5

Output

5

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from AtCoder Educational DP Contest D – Knapsack 1. Bản FULLHOUSE DEV đã biên tập bối cảnh/format và ràng buộc khi cần để khớp scope-lock của khóa học.