Maximum Sum of Ratings within Storage Limit

You are given ( n ) songs, each with a storage size and a rating. Your task is to choose a subset of these songs so that the total size does not exceed a given limit ( S ), while maximizing the total sum of ratings. This problem is analogous to the classic 0/1 knapsack problem, where you wish to maximize ( \sum_{i=1}^{n} r_i ) subject to ( \sum_{i=1}^{n} s_i \leq S ), where ( s_i ) and ( r_i ) denote the size and rating of the ( i^{th} ) song respectively. If no valid combination is found, output 0.

inputFormat

The first line contains two integers ( n ) and ( S ): the number of songs and the storage limit respectively. Each of the next ( n ) lines contains two integers: the size and the rating of one song.

outputFormat

Output a single integer representing the maximum total rating sum that can be achieved without exceeding the storage limit ( S ).## sample

4 10
5 10
4 7
6 6
2 5

17