Ba lô theo tổng giá trị

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

Trọng lượng tối đa W rất lớn nên DP theo capacity không khả thi. Tuy nhiên tổng giá trị của các vật nhỏ hơn đáng kể.

Yêu cầu

Tìm tổng giá trị lớn nhất của một tập vật có tổng trọng lượng không vượt W.

Input

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

Output

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

Ràng buộc

• 1 <= n <= 100
• 1 <= W <= 10^18
• 1 <= w_i <= 10^9
• 1 <= v_i <= 1000
• Tổng v_i <= 10^5

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

3 10
11 100
5 4
5 5

Output

9

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 E – Knapsack 2. 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.