HardDynamic Programming2000 ms256 MB
Certification Roadmap
Given module study times and readiness values, choose modules whose total time is at most `T` and maximize total readiness.
Statement
Given module study times and readiness values, choose modules whose total time is at most `T` and maximize total readiness.
Input
First line: `n T`. Next `n` lines: `time readiness`.
Output
Print the maximum readiness value.
Constraints
- `1 <= n <= 100`, `1 <= T <= 10000`
Examples
Example 1
Input
3 5
2 10
3 14
4 16Output
24Choose the first two modules for total time 5 and readiness 24.
Sample runs use visible examples. Full submissions are checked securely on the server, and private test cases are not shown in the browser.