import java.util.*;

// Unbounded Knapsack Problem

public class uknapp 
{
    public static void main(String[] a) 
    {
        // Random knapsack for checking methods against each other
        // Number of items
        int N = 1000;
        
        // Item descriptions
        vals = new int[N];
        weight = new int[N];
        
        // Capacity of sack
        int cap = 500;
        
        // Generate random values
        for (int i = 0; i < N; i++) 
        {
            vals[i] = (int)(Math.random() * 1000);
            weight[i] = (int)(Math.random() * cap) + 1;
        }
        
        /*
        // Method for doing custom knap sack items
        vals = new int[]{10,1,13,5,7};
        weight = new int[]{9, 2, 8, 5, 6};
        
        // Capacity of sack
        int cap = 18;
        */
        
        // ----------------------------------
        //           Recursive DP
        // ----------------------------------
        // Create the memo table
        memo = new int[cap + 1][vals.length + 1];
        
        // Fill the table with the sentinel
        for (int[] tmp : memo)
            Arrays.fill(tmp, SENT);
        
        // Compute the maximum value for the given capacity using the
        // recursive method
        System.out.println(f(cap, 0));
        
        // ----------------------------------
        //        Space Saving Method
        // ----------------------------------
        // Space Saving (1 array)
        int[] firstArr = new int[cap + 1];
        int n = vals.length;
        
        // Check each item for potential improvements
        for (int i = 0; i < n; i++) 
        {
            // For each capacity check if the item can improve the solution
            for (int j = 0; j <= cap; j++) 
            {
                // Bounds check
                if (j + weight[i] < cap + 1) 
                {
                    // Check if we can improve by using the item
                    if (firstArr[j + weight[i]] < firstArr[j] + vals[i]) 
                    {
                        // Use the item
                        firstArr[j + weight[i]] = firstArr[j] + vals[i];
                    }
                }
            }
        }
        
        // Print the answer
        System.out.println(firstArr[cap]);
    }
    
    public static int[] vals, weight;
    public static int[][] memo;
    public static int SENT = -1;
    
    public static int f(int cap, int index) 
    {
        
        // Overfilled 
        if (cap < 0 )
            return -987654321;
            
        // Check if computed previously
        if (memo[cap][index] != SENT)
            return memo[cap][index];
        
        // Check end of the list
        if (index == vals.length)
            return 0;
        
        // Take item
        int first = f(cap - weight[index], index) + vals[index];
        
        // Don't take
        int second = f(cap, index + 1);
        
        // Check which potential solution is better
        if (first < second)
            memo[cap][index] = second;
        else
            memo[cap][index] = first;
        
        // Return the best value found
        return memo[cap][index];
    }
}