Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Dropping the stones
Time Limit: 2000MSMemory Limit: 65536K
Total Submissions: 1827Accepted: 658

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.

Sample Input

4 2
2 2
2 2
1 1
1 1

Sample Output

3

Source

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