Maximizing Usefulness

You are given a list of tasks, where each task is represented as a pair \( (t, u) \), with \( t \) being the time required to complete the task and \( u \) the corresponding usefulness index. You are also provided with a total available time \( T \). Your goal is to select a subset of these tasks in such a way that the total time taken does not exceed \( T \) and the sum of their usefulness indices is maximized.

This is a classic optimization problem that can be solved using a dynamic programming approach. The recurrence formula used is:

[ \text{dp}[i][w] = \max\Bigl(\text{dp}[i-1][w],; \text{dp}[i-1][w - t_i] + u_i\Bigr) \quad \text{for } t_i \le w, ]

Otherwise, \( \text{dp}[i][w] = \text{dp}[i-1][w] \).

Read the input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

The input is provided via standard input (stdin) and has the following format:

N T
t1 u1
 t2 u2
 ...
 tN uN

Here, the first line contains two integers \( N \) (the number of tasks) and \( T \) (the total available time). Each of the following \( N \) lines contains two integers \( t_i \) and \( u_i \) representing the time required and the usefulness of the \( i^{th} \) task.

outputFormat

Output a single integer representing the maximum sum of usefulness indices that can be achieved without exceeding the available time \( T \). The result should be printed to standard output (stdout).

## sample

4 6
1 4
2 3
3 5
5 8

12