Maximize Total Satisfaction

You are given a set of cities, each represented by a pair of integers (d) and (s) where (d) is the travel distance to the city and (s) is the satisfaction obtained from visiting it. You also have a travel distance limit (m). Your task is to choose a subset of these cities such that the total travel distance does not exceed (m) and the total satisfaction is maximized. This problem can be modeled as a 0/1 knapsack problem, where the objective is to maximize the sum of satisfactions while keeping the sum of travel distances within the limit (m).

inputFormat

The input is given via standard input (stdin) in the following format:\ The first line contains two integers (n) and (m), where (n) represents the number of cities and (m) is the maximum travel distance allowed.\ This is followed by (n) lines, each containing two integers (d) and (s). Here, (d) is the travel distance required for a city and (s) is the satisfaction obtained from that city.

outputFormat

Output a single integer to standard output (stdout), representing the maximum total satisfaction that can be achieved without exceeding the travel distance (m).## sample

3 100
30 5
50 8
70 7

13