CHARM - Chuỗi hạt ngọc trai
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Tại cửa hàng có ~N~ (~1 ≤ N ≤ 3402~) hạt ngọc trai. Hạt thứ k có khối lượng ~W_k~ (~1 ≤ W_k ≤ 400~) và giá trị là ~D_k~ (~1 ≤ D_k ≤ 100~).
Bessie muốn mua một số hạt ngọc trai để xâu thành chuỗi hạt tặng Austin, nhưng khối lượng của chuỗi không được vượt quá ~M~. (1 ≤ M ≤ 12800) Hãy giúp Bessie chọn được chuỗi hạt có giá trị lớn nhất thỏa mãn yêu cầu trên.
Quy ước: Giá trị của một chuỗi hạt bằng tổng giá trị của mỗi hạt trong chuỗi đó.
Input
- Dòng đầu tiên ghi số ~N~ và ~M~
- ~N~ dòng tiếp theo, dòng thứ ~k~ (~1 ≤ k ≤ N~) ghi hai số nguyên ~W_k~ và ~D_k~.
Output
Một dòng duy nhất đưa ra giá trị lớn nhất có thể của chuỗi hạt.
Sample
Input #1
4 6
1 4
2 6
3 12
2 7
Output #1
23
Hint
Trong ví dụ trên, chuỗi hạt tìm được sẽ bao gồm đúng 3 hạt ngọc đó là các hạt ở vị trí thứ 1, thứ 3, và thứ 4.
Problem source: Kc97ble - Free Contest
Bình luận
Quy hoạch đồng nhưng cần tối ưu 2 chiều hoặc đưa luôn về 1 chiều.