当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
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.
4 2 2 2 2 2 1 1 1 1
3
| 时间上限 | 内存上限 |
| 2000 | 65536 |