import java.util.*;

public class knap01 {
    public static void main(String[] a) {
        vals = new int[]{10,1,13,5,7};
        weight = new int[]{9, 2, 8, 5, 6};
        int cap = 18;
        
        
        // Still inefficient for memory usage
        // TODO : As an extension see if you can muse only cap + 1
        // HINT : Bottom up approach can be very helpful!
        memo= new int[cap + 1][vals.length + 1];
        
        // Fill the table with the sentinel
        for (int[] tmp : memo)
            Arrays.fill(tmp, SENT);
        
        System.out.println(f(cap, 0));
        
    }
    
    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 + 1) + vals[index];
        
        // Don't take
        int second = f(cap, index + 1);
        
        if (first < second)
            memo[cap][index] = second;
        else
            memo[cap][index] = first;
        
        return memo[cap][index];
    }
}