using System;

public class Program

{

    // A utility function that returns

    // maximum of two integers

    static int max(int a, int b)

    {

         return (a > b) ? a : b;

    }

    // Returns the maximum value that

    // can be put in a knapsack of

    // capacity W

    static int knapSack(int W, int[] wt,

                        int[] val, int n)

    {

        int i, w;

        int[, ] K = new int[n + 1, W + 1];

        for (i = 0; i <= n; i++)

        {

            for (w = 0; w <= W; w++)

            {

                if (i == 0 || w == 0)

                    K[i, w] = 0;

                else if (wt[i - 1] <= w)

                    K[i, w] = Math.Max(

                        val[i - 1]

                        + K[i - 1, w - wt[i - 1]],

                        K[i - 1, w]);

                else

                    K[i, w] = K[i - 1, w];

            }

        }

        return K[n, W];

    }

    // Returns the maximum value that can

    // be put in a knapsack of capacity W

    static int knapSackhHard(int W, int[] wt,

                        int[] val, int n)

    {

        // Base Case

        if (n == 0 || W == 0)

            return 0;

        // If weight of the nth item is

        // more than Knapsack capacity W,

        // then this item cannot be

        // included in the optimal solution

        if (wt[n - 1] > W)

            return knapSackhHard(W, wt,

                            val, n - 1);

        // Return the maximum of two cases:

        // (1) nth item included

        // (2) not included

        else

            return max(val[n - 1]

                       + knapSackhHard(W - wt[n - 1], wt,

                                  val, n - 1),

                       knapSackhHard(W, wt, val, n - 1));

    }

    static void Main()

    {

        int[] val = new int[] { 100, 3, 7,37 };

        int[] wt = new int[] { 10000,5000, 8000,9000 };

        int W = 20000;

        int n = val.Length;

        Console.WriteLine(knapSack(W, wt, val, n));

        Console.WriteLine(knapSackhHard(W, wt, val, n));

    }

}