22663_Droppingthestones

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 at least 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.

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 a single line with total cost of stones in the bunker В.

4 2
2 2
2 2
1 1
1 1

3