import java.lang.*;
import java.util.*;

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

    int 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 (Stock stock : stocks) {
            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<Stock> chooseStocks(Stock[] stocks, int priceLimit) {
        // TODO: 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);
        }
        Collections.reverse(result);

        return result;
    }

    public static void main(String[] args) {
        int input;
        Scanner scanner = new Scanner(System.in);
        ArrayList<Stock> choices = new ArrayList<Stock>();
        int priceLimit = 0;
        boolean run = false;

        do {
            System.out.println("1. Add a stock");
            System.out.println("2. Buying power");
            System.out.println("3. Display stocks and buying power");
            System.out.println("4. Run");
            System.out.println("5. Exit");

            input = scanner.nextInt();
            scanner.nextLine();

            switch (input) {
                case 1:
                    System.out.println("Type 'Stock Ticker, Price (USD), "
                        + "Value'");
                    String stockInput = scanner.nextLine();
                    String[] stockTraits = stockInput.trim()
                        .split("\\s*,\\s*");
                    try {
                        choices.add(new Stock(Integer.parseInt(stockTraits[1]),
                            Integer.parseInt(stockTraits[2]), stockTraits[0]));
                    } catch (NumberFormatException e) {
                        System.out.println("Invalid input - must enter: "
                            + "ticker, #, #");
                    } catch (ArrayIndexOutOfBoundsException e) {
                        System.out.println("Wrong number of inputs - must "
                            + "enter: ticker, #, #");
                    }
                    break;
                case 2:
                    System.out.println("How much money do you have to "
                            + "allocate?");
                    priceLimit = Integer.parseInt(scanner.nextLine());
                    break;
                case 3:
                    System.out.println(choices);
                    System.out.println(priceLimit);
                    break;
                case 4:
                    run = true;
                    break;
                case 5:
                    System.exit(0);
                    break;
                default:
                    System.out.println("Invalid input - must enter a number "
                            + "between 1 and 5");
                    break;
            }
        }
        while(!run);
        scanner.close();

        // Stock stocks[] = {new Stock(3, 10, "A"), new Stock(4, 14, "B")};
        ArrayList<Stock> result = chooseStocks(choices.toArray(
            new Stock[choices.size()]), priceLimit);

        for (Stock stock : result) {
            System.out.println(stock);
        }
    }
}

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;
    }

    @Override
    public String toString() {
        return "Ticker: " + ticker + " price: " + price + " value: " + value;
    }
}