Dividing the Treasures

Time limit10sMemory limit1024 MB

Summary

Give each treasure to Anna, to Bruno, or to nobody so the two market totals differ by at most D and Bruno's preciousness minus Anna's is maximal.

Level: Medium7 of 10
Topics: Divide and conquer, Brute force, Sorting
Solved: No attempts yet

Problem

The thieves Anna and Bruno sneak into a rich man's mansion and find $N$ treasures, numbered treasure 1 through treasure $N$ . The two of them decide to divide the treasures. Anna takes some of the treasures, then Bruno takes some of the ones that are left. The two of them cannot take the same treasure. Anna and Bruno may each take no treasure at all. Whatever nobody takes stays in the mansion, so a treasure that neither of them takes is allowed.

Every treasure has two values, a market value and a preciousness. If the absolute difference between the total market value of the treasures Anna takes and the total market value of the treasures Bruno takes is at most $D$ , Anna considers the division fair and is satisfied. Bruno, on his side, wants treasures of greater preciousness than Anna's.

Divide the treasures so that Anna is satisfied. Find the maximum value of the total preciousness of the treasures Bruno takes minus the total preciousness of the treasures Anna takes.

Input

The input consists of $1 + N$ lines.

The first line contains two integers $N$ and $D$ separated by a space ( $1 \le N \le 30$ , $0 \le D \le 10^{15}$ ). There are $N$ treasures, and Anna is satisfied when the absolute difference between the total market value she takes and the total market value Bruno takes is at most $D$ .

Line $i$ of the following $N$ lines ( $1 \le i \le N$ ) contains two integers $X_i$ and $Y_i$ separated by a space ( $0 \le X_i \le 10^{15}$ , $0 \le Y_i \le 10^{15}$ ). Treasure $i$ has market value $X_i$ and preciousness $Y_i$ .

Output

Print in one line the maximum value of the total preciousness of the treasures Bruno takes minus the total preciousness of the treasures Anna takes, over all divisions that satisfy Anna.

Hint

In the first example, suppose Anna takes treasures 2, 3 and 5, and Bruno takes treasures 1 and 6. The total market value is 130 for Anna and 120 for Bruno. The absolute difference 10 is at most $D = 15$ , so Anna is satisfied. The total preciousness is 400 for Anna and 1600 for Bruno, so the total preciousness Bruno takes minus the total preciousness Anna takes is 1200. That is the maximum.

Examples4

Example 1

Input

Expected output

Example 2

Input

5 0
0 1000000000000000
0 1000000000000000
1 1
1000000000000000 0
1000000000000000 0

Expected output

2000000000000000

Example 3
Input
```
1 0
0 5
```
Expected output
```
5
```
Example 4
Input
```
4 2
10 1
11 2
12 3
13 4
```
Expected output
```
2
```