3400 -- Dropping the stones

Language:

Dropping the stones

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 1992		Accepted: 708

Description

You have N stones (1 ≤ N ≤ 10), each stone is characterized by weight p_i and cost v_i (i = 1, ... , N). You should drop these stones by a gutter into one of the two bunkers: A or В.

The mechanism of receiving bunkers switching works as follows. The stones are dropping into one of the bunkers until the weight of this bunker’s content will exceed the weight of stones in other bunker by more than D. Then the gutter switches to the other bunker. At the beginning both bunkers are empty, and the first stone falls into the bunker А.

The task is to collect stones with maximum total cost in bunker B after all stones have been dropped.

Input

The input consists of N + 1 lines. The first line contains values N and D separated by one or several spaces. The next lines contain values p_i and v_i, also separated by spaces. All input data (except N) are integers from 0 to 10000.

Output

The output contains a single line with total cost of stones in the bunker B.

Sample Input

Sample Output

Source

Northeastern Europe 2001, Western Subregion