Cake Knapsack Problem

In this problem, you are given (N) cakes, where each cake has a weight (w_i) and a price (p_i). Your task is to determine the maximum price you can achieve by selecting a subset of these cakes such that their total weight does not exceed a given limit (W). This is a classic 0/1 knapsack problem and can be solved using dynamic programming. The recurrence relation is given by: [ \text{dp}[i][w] = \begin{cases} \text{dp}[i-1][w] & \text{if } w_i > w,\ \max\big(\text{dp}[i-1][w],; \text{dp}[i-1][w-w_i]+p_i\big) & \text{if } w_i \leq w. \end{cases} ] Here, (\text{dp}[i][w]) represents the maximum price that can be achieved with the first (i) cakes and with a weight limit of (w).

inputFormat

The input is given via standard input (stdin). The first line contains two integers (N) and (W), representing the number of cakes and the maximum allowed weight, respectively. This is followed by (N) lines, each containing two integers: the weight (w_i) and price (p_i) of the (i)-th cake.

outputFormat

Output via standard output (stdout) a single integer: the maximum price that can be achieved by selecting a subset of cakes such that their total weight does not exceed (W).## sample

4 10
5 10
4 40
6 30
3 50

90