The Bag of Gold Again

You are given an empty bag that is supposed to be filled with gold, and it can carry at max W kgs of gold in it.

You are given N samples of gold, with the ith of them weighing Wi and having value Vi.

Your task is to fill the bag with atmost W kgs of gold such that the total value of the gold inside the bag is maximum.

Unlike last time, this time whenever you choose to pick a sample of gold, you have to take it completely, i.e. you cannot break down samples. You either pick the entire sample of gold, or you dont pick the sample at all.

INPUT

First line contains two integers, N and W.
Second onwards, there are N lines with each of them containing two integers, first one being the weight of the sample and the second one being the value of the sample

OUTPUT

Print one number, the maximum attainable value when the bag is filled with atmost W kgs of gold.

CONSTRAINTS

1 ≤ N ≤ 103
1 ≤ W ≤ 103
1 ≤ weights, values ≤ 103

Sample Input 0

1
3 50
10 60
20 100
30 120

Sample Output 0

220

Solution :

import java.io.*;

import java.util.*;

public class Solution {

    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);

        int t=sc.nextInt();

        while(t-->0)

        {

            int n=sc.nextInt();

            int weight=sc.nextInt();

            int w[]=new int[n];

            int c[]=new int[n];

            for(int x=0;x<n;x++)

            {

                w[x]=sc.nextInt();

                c[x]=sc.nextInt();

            }

            int dp[][]=new int[n+1][weight+1];

            for(int x=1;x<=weight;x++)

            {

                for(int y=1;y<=n;y++)

                {

                    dp[y][x]=dp[y-1][x];

                    if(w[y-1]<=x)

                    {

                        dp[y][x]=Math.max(dp[y][x],dp[y-1][x-w[y-1]]+c[y-1]);

                    }

                    else

                    {

                        

                    }

                }

            }

            System.out.println(dp[n][weight]);

        }

    }

}