Maximum Points Challenge

You are given a set of problems, each with a specific point value and a time requirement, along with a total available time. Your task is to determine the maximum points you can earn by choosing a subset of the problems such that the total time required does not exceed the available time. This is a typical 0/1 knapsack problem. The recurrence relation for the dynamic programming solution is given by:

$dp[i][t] = \max(dp[i-1][t],\, dp[i-1][t-t_i]+p_i)$

where $p_i$ is the points for the i-th problem and $t_i$ is its time requirement. You are allowed to solve each problem at most once.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers n (the number of problems) and T (the total available time), separated by a space.
• Each of the next n lines contains two integers: the points awarded for a problem and its time requirement, separated by a space.

outputFormat

Output a single integer to stdout which is the maximum total points that can be obtained without exceeding the time limit.

3 50
100 20
200 30
50 10

300