Maximize Profit in Job Scheduling

You are given a set of N jobs and T available days. Each job i requires D_i days to complete and yields a profit of P_i. Your task is to select a subset of jobs such that the total duration does not exceed T days and the total profit is maximized.

In other words, find the maximum total profit subject to

\( \sum_{i \in S} D_i \leq T \)

where S is the set of jobs chosen.

If no set of jobs can be completed within the given days, output 0.

inputFormat

The input is given via standard input in the following format:

N T
D1 P1
D2 P2
... 
DN PN

Where:

• N is the number of jobs.
• T is the total available days.
• Each of the next N lines contains two integers: the duration Di and profit Pi for job i.

outputFormat

Output a single integer representing the maximum profit that can be earned within T days.

## sample

4 5
2 10
1 20
2 15
1 10

45