Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Dropping the stones
Time Limit: 2000MSMemory Limit: 65536K
Total Submissions: 1955Accepted: 698


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.


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.


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

Sample Input

4 2
2 2
2 2
1 1
1 1

Sample Output



Northeastern Europe 2001, Western Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator