Ngân sách tài liệu

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

Có n tài liệu; tài liệu i có giá p_i và điểm kiến thức v_i. Mỗi tài liệu mua tối đa một lần, ngân sách không quá x.

Yêu cầu

Tối đa hóa tổng điểm kiến thức.

Input

Dòng 1 n x; dòng 2 giá; dòng 3 điểm.

Output

In tổng điểm lớn nhất.

Ràng buộc

• 1 <= n <= 1000
• 1 <= x <= 10^5
• 1 <= p_i <= 10^5
• 1 <= v_i <= 10^6

Chấm điểm

Ví dụ 1

Input

4 10
4 8 5 3
5 12 8 1

Output

13

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 5
6 7 8
10 20 30

Output

0

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.

Gợi ý

Trước khi code, hãy viết rõ ý nghĩa của trạng thái, các trạng thái tiền nhiệm và thứ tự tính sao cho mọi dependency đã có giá trị.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Book Shop. 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.