分数: 500 点
问题陈述
日本餐厅“帝石寿司”是一家只有一个圆形柜台的朴素餐厅。计数器的外周长是 C 米。顾客不能进入柜台内。
中桥进入定石寿司,被引导到柜台。现在,有 N 柜台上有几块寿司(醋饭加海鲜等)。从中桥站立的点到中桥站的点顺时针测量的距离 i第一个寿司被放置,是 x_i 米。另外, i第寿司的营养价值为 v_i 千卡。
中桥可以在柜台周围自由行走。当他到达放置寿司的位置时,他可以吃该寿司并吸收其营养(自然地,寿司会消失)。然而,当他走路时,他会消耗 1 每米千卡。
每当他满意时,他可以从任何地方离开餐厅(他不必返回初始地点)。权衡下来,他在离开之前最多能摄入多少营养?即摄入的总营养减去消耗的总能量的最大可能值是多少?假设没有其他顾客,柜台上也不会添加新的寿司。另外,由于中桥体内有充足的营养,所以假设无论他走路多少,消耗多少能量,他都不会饿死。
约束
- 1 ≤ N ≤ 10^5
- 2 ≤ C ≤ 10^{14}
- 1 ≤ x_1 < x_2 < ... < x_N < C
- 1 ≤ v_i ≤ 10^9
- 输入中的所有值都是整数。
分项分数
- 300 通过满足以下条件的测试集将获得积分 N ≤ 100.
输入
输入由标准输入按以下格式给出:
N C x_1 v_1 x_2 v_2 : x_N v_N
输出
如果中桥最多能容纳 c 离开餐厅前平衡千卡,打印 c.
示例输入 1
3 20 2 80 9 120 16 1
示例输出 1
191
柜台上有三个寿司,周长为 20 米。如果他从起始位置顺时针走两米,他可以吃一个寿司 80 千卡。如果他顺时针再走七米,他就可以吃一个寿司 120 千卡。如果他现在离开,摄入的总营养是 200 千卡,消耗的总能量为 9 千卡,这样他就可以摄入 191 平衡千卡,这是最大可能值。
示例输入 2
3 20 2 80 9 1 16 120
示例输出 2
192
第二个和第三个寿司已互换。同样,如果他从起始位置顺时针走两米,他可以吃一个寿司 80 千卡。这次如果他再逆时针走六米,他就能吃一个寿司 120 千卡。如果他现在离开,摄入的总营养是 200 千卡,消耗的总能量为 8 千卡,这样他就可以摄入 192 平衡千卡,这是最大可能值。
示例输入 3
1 100000000000000 50000000000000 1
示例输出 3
0
尽管到目前为止唯一的寿司不适合 32位整数,营养价值低,应该立即离开,什么也不做。
示例输入 4
15 10000000000 400000000 1000000000 800000000 1000000000 1900000000 1000000000 2400000000 1000000000 2900000000 1000000000 3300000000 1000000000 3700000000 1000000000 3800000000 1000000000 4000000000 1000000000 4100000000 1000000000 5200000000 1000000000 6600000000 1000000000 8000000000 1000000000 9300000000 1000000000 9700000000 1000000000
示例输出 4
6500000000
上述所有样本输入都包含在部分分数的测试集中。