题目描述

你有$N$块石头（$1 \leq N \leq 10$），每块石头由重量$p_i$和价值$v_i$（$i = 1, \dots, N$）描述。你需要将这些石头通过一个槽道放入两个仓室A或B中的一个。

仓室切换的机制如下：石头会持续落入某个仓室，直到该仓室的总重量超过另一个仓室的总重量且差值大于$D$。此时槽道会切换到另一个仓室。初始时两个仓室均为空，且第一块石头必须落入仓室A。

任务是在所有石头都落入后，计算仓室B中石头的最大总价值。

输入格式

输入由$N+1$行组成。第一行包含两个整数$N$和$D$，用一个或多个空格分隔。接下来的$N$行每行包含两个整数$p_i$和$v_i$，分别表示第$i$块石头的重量和价值。所有输入数据（除$N$外）均为$0$到$10000$之间的整数。

输出格式

输出仅一行，包含仓室B中石头的最大总价值。

输入数据示例1

4 2  
2 2  
2 2  
1 1  
1 1  

输出数据示例1

3  

来源

东北欧2001年西部赛区