403205: GYM101064 L The Knapsack problem

To prepare for the ICPC World Finals 2017, your team attended to a training camp. Glauber "the drinker" Sokolov was the teacher, and all teams had to answer a form so he would know what topics were the best to teach. The first day was introductory and Glauber said he would just go over well-known topics. He said "I noticed you all answered that you knew the Knapsack problem very well, so here is a simple exercise about it, follows directly from the definitions. Solve the knapsack problem with repetitions.".

More formally, given N types of items, each one with a weight and a cost, choose some items such that the sum of its weights does not exceed S, and the sum of costs is maximum. You may choose any number of items of each type.

Solve Glauber's exercise.

On the first line two integers N and S, the number of types of items and the maximum allowed weight.

Each of the next N lines has two integers w_i and c_i, the weight and the cost of the ith type of item.

Limits

• 1 ≤ N, w_i ≤ 10³
• 0 ≤ S, c_i ≤ 10⁹

Print a single integer, the cost of the items you choose.

3 100
14 5
13 2
5 1

35