import java.io.*;

class Knapsack01 {

    /**
     * Builds the DP table and computes the maximum achievable profit.
     *
     * @param weights    weight of each item (1-indexed)
     * @param profits    profit of each item (1-indexed)
     * @param itemCount  number of items
     * @param maxCapacity maximum knapsack weight capacity
     */
    void solve(int[] weights, int[] profits, int itemCount, int maxCapacity) {
        // dpTable[i][j] = max profit using first i items with capacity j
        int[][] dpTable = new int[itemCount + 1][maxCapacity + 1];

        // Base cases: 0 items or 0 capacity yields 0 profit
        for (int capacity = 0; capacity <= maxCapacity; capacity++)
            dpTable[0][capacity] = 0;
        for (int i = 0; i <= itemCount; i++)
            dpTable[i][0] = 0;

        // Fill the DP table
        for (int i = 1; i <= itemCount; i++) {
            for (int j = 0; j <= maxCapacity; j++) {
                if (weights[i] <= j) {
                    // Item i can fit: choose the better option
                    // Option A: include item i  -- profits[i] + best profit for remaining capacity
                    // Option B: exclude item i  -- same as best profit without item i
                    int profitWithItem    = profits[i] + dpTable[i - 1][j - weights[i]];
                    int profitWithoutItem = dpTable[i - 1][j];
                    dpTable[i][j] = Math.max(profitWithItem, profitWithoutItem);
                } else {
                    // Item i does not fit: carry forward the profit without it
                    dpTable[i][j] = dpTable[i - 1][j];
                }
            }
        }

        // Trace back through the DP table to find which items were selected
        findSelectedItems(dpTable, itemCount, maxCapacity, weights, profits);
    }

    /**
     * Traces back through dpTable to determine which items were included
     * in the optimal solution.
     */
    void findSelectedItems(int[][] dpTable, int itemCount, int maxCapacity,
                           int[] weights, int[] profits) {
        int[] selectedItems = new int[itemCount + 1];  // 1 = included, 0 = excluded
        int   currentItem   = itemCount;
        int   currentCap    = maxCapacity;
        int   totalProfit   = 0;

        // Walk backwards: if dpTable[i][cap] != dpTable[i-1][cap], item i was included
        while (currentItem > 0 && currentCap > 0) {
            if (dpTable[currentItem][currentCap] != dpTable[currentItem - 1][currentCap]) {
                selectedItems[currentItem] = 1;           // item was taken
                totalProfit               += profits[currentItem];
                currentCap                -= weights[currentItem];  // reduce capacity
            }
            currentItem--;
        }

        // Display results
        System.out.println("Selected items (1 = included, 0 = excluded):");
        for (int i = 1; i <= itemCount; i++) {
            System.out.println("Item " + i + ": " + selectedItems[i]);
        }
        System.out.println("Maximum Profit: " + totalProfit);
    }
}

class Knapsack01Main {
    public static void main(String[] args) throws IOException {
        Knapsack01 knapsack = new Knapsack01();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("How many items?");
        int itemCount = Integer.parseInt(reader.readLine());

        System.out.println("Enter the knapsack capacity:");
        int maxCapacity = Integer.parseInt(reader.readLine());

        int[] profits = new int[itemCount + 1];  // 1-indexed
        int[] weights = new int[itemCount + 1];  // 1-indexed

        System.out.println("Enter profit and weight for each item:");
        for (int i = 1; i <= itemCount; i++) {
            System.out.print("Profit of item " + i + ": ");
            profits[i] = Integer.parseInt(reader.readLine());
            System.out.print("Weight of item " + i + ": ");
            weights[i] = Integer.parseInt(reader.readLine());
            System.out.println();
        }

        knapsack.solve(weights, profits, itemCount, maxCapacity);
    }
}