AT_joi2015yo_f.財宝 (Treasures)

盗贼 Anna 和 Bruno 潜入了一位大富豪的宅邸，发现了从第 $1$ 件到第 $N$ 件共 $N$ 件宝物。现在需要将这些宝物在 Anna 和 Bruno 之间分配。Anna 可以取其中一些宝物，Bruno 可以从剩下的宝物中取一些。每件宝物只能被一个人取走，不能两个人都取同一件宝物。Anna 和 Bruno 也可以什么都不取。同时，也允许有些宝物两个人都不取，留在宅邸中。

每件宝物都有两个属性：“市场价值”和“贵重度”。如果 Anna 取走的宝物的市场价值总和与 Bruno 取走的宝物的市场价值总和的差的绝对值不超过 $D$，Anna 就会觉得分配公平并感到满意。而 Bruno 希望自己拿到的宝物的贵重度总和尽可能比 Anna 多。

请你在保证 Anna 满意的前提下，求出 Bruno 取走的宝物的贵重度总和减去 Anna 取走的宝物的贵重度总和的最大值。

输入共 $1+N$ 行。

第 $1$ 行包含两个整数 $N, D$（$1 \leq N \leq 30$，$0 \leq D \leq 10^{15}$），表示宝物的数量为 $N$，以及 Anna 满意的市场价值差的绝对值上限为 $D$。

接下来的 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含两个整数 $X_i, Y_i$（$0 \leq X_i \leq 10^{15}$，$0 \leq Y_i \leq 10^{15}$），表示第 $i$ 件宝物的市场价值为 $X_i$，贵重度为 $Y_i$。

在给定的 $5$ 组输入数据中，输入 $1$ 满足 $N \leq 10$，输入 $2$ 满足 $D = 0$。

请输出在 Anna 满意的前提下，Bruno 取走的宝物的贵重度总和减去 Anna 取走的宝物的贵重度总和的最大值。

样例解释 1

在样例输入 $1$ 中，如果 Anna 取第 $2$、第 $3$ 和第 $5$ 件宝物，Bruno 取第 $1$ 和第 $6$ 件宝物，则 Anna 取走的宝物的市场价值总和为 $130$，Bruno 为 $120$，两者差的绝对值为 $10$，不超过 $D=15$，所以 Anna 满意。此时 Anna 取走的宝物的贵重度总和为 $400$，Bruno 为 $1\,600$，两者相减为 $1\,200$，这是最大值。

由 ChatGPT 4.1 翻译