配点: 100 点
問題
小偷安娜和布鲁诺潜入百万富翁的豪宅并偷走了宝藏。 来自 1 的宝藏 至 N 最多 N 宝藏。决定将这些宝藏分配给安娜和布鲁诺。安娜拿走了一些宝藏,布鲁诺拿走了一些剩余的宝藏。同样的宝藏 2 人们无法接受。安娜和布鲁诺有宝藏 您甚至不必参加 1 。还有,剩下的宝物会留在宅邸里,所以2 拥有别人拿不到的宝藏也没关系。
每件宝物都有“市场价值”和“价值”。 2 两个值是固定的。安娜所拿走的宝物市场价值之和与布鲁诺所拿走的宝物市场价值之和之差的绝对值为 D 如果小于这个值,安娜就会满意并认为这是公平的。另一方面,布鲁诺想要一件比安娜更有价值的宝藏。
当宝物分配到安娜满意的时候,求布鲁诺拿走的宝物总价值减去安娜拿走的宝物总价值中的最大值。
入力
输入是 1 + N 行组成。
1 行中, 请输出第2 整数 N, D (1 \leqq N \leqq 30,0 \leqq D \leqq 10^{15})以空格作为分隔符。这意味着宝藏的数量是 N ,则安娜所拿走的宝物市值总和与布鲁诺所拿走的宝物市值总和之差的绝对值为 D 如果低于,安娜就满意了。
继续 N 行 i 行目 (1 \leqq i \leqq N)有2 整数 X_i, Y_i (0 \leqq X_i \leqq 10^{15},0 \leqq Y_i \leqq 10^{15})以空格作为分隔符。这是一个宝藏 i 的市场价值是 X_i 而珍贵的是 Y_i 。
给出 它是 5 在输入数据中,输入 1 中 由于 N \leqq 10 满意。另外,输入 在 2 中 由于 D = 0 很满意。
出力
当宝物分配到安娜满意的时候,计算布鲁诺拿走的宝物的珍贵程度之和减去布鲁诺拿走的宝物的珍贵程度之和所得到的最大值。 在 1 输出为行
入力例 1
6 15 50 900 30 200 40 100 80 600 60 100 70 700
出力例 1
1200
入出力例 1 中,安娜有一个宝藏 2 和宝 拿走 3 和宝 拿走 5 ,布鲁诺会珍惜它。 取 1 和宝 拿走 6 ,安娜所拿走的宝藏总市值为 130,布鲁诺 120 和差值的绝对值 10 是 在 D = 15 。此时安娜所拿走的宝物总价值为 400,布鲁诺 1\,600 ,而布鲁诺所拿走的宝物的珍贵程度之和减去安娜所拿走的宝物的珍贵程度之和得到的值为 1\,200 变为。这是最大值。
入力例 2
5 0 0 1000000000000000 0 1000000000000000 1 1 1000000000000000 0 1000000000000000 0
出力例 2
2000000000000000