You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

* The total value of the items is as large as possible.
* The items have combined weight at most W, that is capacity of the knapsack.



Find the maximum total value of items in the knapsack.

Constraints

* 1 ≤ N ≤ 40
* 1 ≤ vi ≤ 1015
* 1 ≤ wi ≤ 1015
* 1 ≤ W ≤ 1015

Input


N W
v1 w1
v2 w2
:
vN wN


The first line consists of the integers N and W. In the following N lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Examples

Input

4 5
4 2
5 2
2 1
8 3


Output

13


Input

2 20
5 9
4 10


Output

9
import java.util.*;

public class Main {
    static Knap[] knaps;
    static ArrayList<HashMap<Long, Long>> dp = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long w = sc.nextLong();
        knaps = new Knap[n];
        for (int i = 0; i < n; i++) {
            dp.add(new HashMap<>());
            knaps[i] = new Knap(sc.nextLong(), sc.nextLong());
        }
        Arrays.sort(knaps);
        knaps[0].sumV = knaps[0].value;
        knaps[0].sumW = knaps[0].weight;
        for (int i = 1; i < n; i++) {
            knaps[i].sumV = knaps[i - 1].sumV + knaps[i].value;
            knaps[i].sumW = knaps[i - 1].sumW + knaps[i].weight;
        }
        System.out.println(dfw(n - 1, w));
    }
    
    static long dfw(int idx, long weight) {
        if (weight < 0) {
            return Long.MIN_VALUE;
        }
        if (idx < 0) {
            return 0;
        }
        if (dp.get(idx).containsKey(weight)) {
            return dp.get(idx).get(weight);
        }
        if (weight >= knaps[idx].sumW) {
            dp.get(idx).put(weight, knaps[idx].sumV);
            return knaps[idx].sumV;
        }
        long max = Math.max(dfw(idx - 1, weight - knaps[idx].weight) + knaps[idx].value, dfw(idx - 1, weight));
        dp.get(idx).put(weight, max);
        return max;
    }
    
    static class Knap implements Comparable<Knap> {
        long value;
        long weight;
        long sumV;
        long sumW;
        
        public Knap(long value, long weight) {
            this.value = value;
            this.weight = weight;
        }
        
        public int compareTo(Knap another) {
            if (weight == another.weight) {
                return 0;
            } else if (weight < another.weight) {
                return -1;
            } else {
                return 1;
            }
        }
    }
}
