package com.company;

import java.io.File;
import java.io.FileNotFoundException;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static double maxCost = 0;
    public static double W = 0;

    public static class Item implements Comparable<Item>
    {
        int cost, weight;
        boolean used;
        public Item(int cost, int weight) {
            this.cost = cost;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Item{" +
                    "cost=" + cost +
                    ", weight=" + weight +
                    '}';
        }

        @Override
        public int compareTo(Item o) {
            long l1 = cost * o.weight;
            long l2 = o.cost * weight;
            return -Long.compare(l1, l2);
        }
    }

    public void run(Item[] items, int i, double curWeight, double curCost) throws FileNotFoundException {

        if (i <= items.length - 1)
        {
            if (curWeight + items[i].weight <= W )
            {
                items[i].used = true;
                run(items, i + 1, curWeight + items[i].weight, curCost + items[i].cost);

            }

            else
            {
                items[i].used = false;
                run(items, i + 1, curWeight, curCost);
            }
        }

        if (maxCost < curCost && W >= curWeight)
        {
            for (Item item: items) {
                if (item.used)
                {
                    maxCost += (double)item.cost;
                }
            }
            run(items, i + 1, curWeight, curCost);
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new File("input.txt"));
        int n = input.nextInt();
        W = input.nextInt();
        Item[] items = new Item[n];
        System.out.println("Вес рюкзака: " + W);
        for (int i = 0; i<n; i++)
        {
            items[i] = new Item(input.nextInt(), input.nextInt());
        }
        System.out.println("Список предметов:");
        for (Item item: items) {
            System.out.println(item);
        }

        System.out.println();
        int i = 0;
        double curWeight = 0, curCost = 0;

        long startTime = System.nanoTime();;
        Arrays.sort(items);
        new Main().run(items, i, curWeight, curCost);
        long finishTime = System.nanoTime();

        System.out.println("Оптимальная стоимость предметов: " + maxCost);
        System.out.println("Время работы алгоритма ветвей и границ для рюкзака: " + (finishTime-startTime) + " ns");
    }
}