Maximum Dish Satisfaction

You are given a list of dishes. Each dish has a cooking time and an associated satisfaction value. Polycarp wants to maximize his total satisfaction by choosing a subset of these dishes such that the sum of their cooking times does not exceed a given time limit \( T \). The task is to compute the maximum total satisfaction value that can be achieved.

The problem can be modeled using a 0/1 knapsack approach with the following recursive relation:

[ dp[t] = \max\left(dp[t],; dp[t - time] + satisfaction\right) \quad \text{for } t \geq time, ]

where dp[t] is the maximum satisfaction achievable in time \( t \). Dishes are processed one by one without repetition.

inputFormat

The input is given through standard input (stdin) and is formatted as follows:

• The first line contains two integers \( n \) and \( T \) where \( n \) is the number of dishes and \( T \) is the total time available.
• The next \( n \) lines each contain two integers: the cooking time and the satisfaction value of a dish.

outputFormat

Output a single integer representing the maximum total satisfaction value that Polycarp can achieve within the given time \( T \). The output is printed to standard output (stdout).

## sample

4 10
5 10
4 40
6 30
3 50

90

</p>