import java.util.*;
import java.io.*;

public class Stock {
    int price, value;
    String ticker;

    public Stock() {
		price = 0;
		value = 0;
		ticker = "";
    }

    public Stock(int price, int value, String ticker) {
		this.price = price;
		this.value = value;
		this.ticker = ticker;
    }
}

public class Backpointer {
    static Stock NOTHING = new Stock(1, 0, "");

    int previousValue, totalValue;
    Stock stock;

    public Backpointer(int previousValue, Stock stock) {
		this.stock = stock;
		this.totalValue = previousValue + stock.value;
    }

	public static Backpointer chooseBackpointer(Stock stocks[],
		ArrayList<Backpointer> backpointers) {

		int currentPrice = backpointers.size();
		Backpointer best = 
		new Backpointer(backpointers.get(currentPrice - 1).totalValue, NOTHING);
		for (int i = 0; i < stocks.length; i++) {
    		Stock stock = stocks[i];	
	    	int previousPrice = currentPrice - stock.price;
	    	if (previousPrice >= 0) {
	    		Backpointer candidate = 
	    		new Backpointer(backpointers.get(previousPrice).totalValue, stock);
			    if (candidate.totalValue > best.totalValue) {
	    	    	best = candidate;
			    }
		    }
		}
		return best;
	}

	public static ArrayList chooseStocks(Stock stocks[], int priceLimit) {
		// assert stock values are integers
		
		// create backpointers
		ArrayList<Backpointer> backpointers = new ArrayList<Backpointer>();
		backpointers.add(new Backpointer(0, NOTHING));
		while (backpointers.size() <= priceLimit) {
			backpointers.add(chooseBackpointer(stocks, backpointers));
		}

		// postprocess backpointers
		ArrayList<Stock> result = new ArrayList<Stock>();
		for (int price = priceLimit; price > 0; 
		price -= backpointers.get(price).stock.price) {
			Stock stock = backpointers.get(price).stock;
			if (stock != NOTHING)
				result.add(stock);
			result.add(backpointers.get(price).stock);
		}
		Collections.reverse(result);

		return result;
	}

	public static void main(String[] args) {
		Stock stocks[] = {new Stock(3, 10, "A"), new Stock(4, 14, "B")};
		int priceLimit = 10;
		ArrayList result = chooseStocks(stocks, priceLimit);
	}
}