Dropping the stones
Description
You have N stones (1 ≤ N ≤ 10), each stone is characterized by weight pi and cost vi (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 pi and vi, 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.
4 2
2 2
2 2
1 1
1 13
Source
Northeastern Europe 2001, Western Subregion