Description

The classic 0-1 knapsack problem: There are n items, where the weight of the i-th item is w[i] and its value is c[i]. The task is to select some items to pack into a knapsack with a capacity of m, such that the total weight of the selected items does not exceed m while maximizing the total value.

Input Format

• Line 1: Two integers, n (number of items, n ≤ 3500) and m (knapsack capacity, m ≤ 12880).
• Lines 2..n+1: Each line contains two integers w[i] and c[i], representing the weight and value of the i-th item, respectively.

Output Format

A single line containing the maximum total value achievable.

4 6
1 4
2 6
3 12
2 7

23

Hint

No