← 返回题目列表

AtCoder · pakencamp_2020_day2_f

F. 明年我们将派出20人进入决赛,请做好准备。

中文机器翻译题面 查看原题

配点: 800 点

問題文

今年是20XX年,当你在室内解决问题时,PA实验室的比率会增加。 2 它获得了加倍的能力。 然而,即使在已经成为一种超自然现象的公园俱乐部房间里,对于会员费率的差异也无能为力,有一天,公园俱乐部经理对此感到遗憾,并决定重新平均分配会员费率。

在执行董事计划的那天,有一个 N 俱乐部会员来访。 i 第一个会员正在评分 A_i 和时间 L_i 我进入PA实验室并查看了时间。 离开 R_i 的俱乐部房间。多个成员不会同时进出。
当会员经过俱乐部房间入口时,即进入和离开俱乐部房间时,经理可以从会员价格中选择任意价格。 您可以减去整数并将该金额添加到您的费率中。 但是,在此操作过程中的任何时候,会员和管理员的评分都不得变为负值。

当管理员执行操作时,成员 i 的速率转变如下。在这里, E 是经理的汇率。

  • 进入俱乐部房间之前 A_i 。 当
  • 进入PA实验室。给经理 x (-E \leq x \leq A_i) 我被它吸引。经理、会员 i 费率分别为 它变成 E+x, A_i-x 。
  • 解决 PA 实验室的问题。率是 2 双倍。
  • 离开 PA 实验室。给经理的评价 它变成 y (-E' \leq y \leq A_i')我被它吸引。经理、会员 i 费率分别为 它变成 E'+y, A_i'-y 。在这里, E',A_i' 是因为成员 当时的经理和会员 i 离开俱乐部房间 费率为 i 。

经理从计划开始到结束的费率。 E 不会因出入口操作以外的任何操作而增加或减少。

你的工作是当经理完成所有操作时,找到“除经理之外的所有成员的最低比率”的最大值。 所有

制約

  • 1 \leq N \leq 10^5
  • 1 \leq E \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 1 \leq L_i < R_i \leq 2N (1 \leq i \leq N)
  • L_i, R_i值都不同。

部分点

  • 小課題 1 (50点): 1 \leq N \leq 4, 1 \leq E \leq 3, 1 \leq A_i \leq 3
  • 小課題 2 (200点): R_i < L_j (1 \leq i < j \leq N)
  • 子作业 3(550 分):无附加限制。

入力

输入按以下格式给出。

N\ E
A_1\ A_2\ \dots\ A_{N-1}\ A_N
L_1\ R_1
L_2\ R_2
\vdots
L_N\ R_N

出力

输出问题陈述中指示的值。 答案是 10^{12}或更多,而不是答案 输出 'inf' 。


入力例1

2 2
1 1
1 2
3 4

出力例1

4

此时,经理采取以下操作。

时间 1:费率会员 1 1 给予。会员1的费率是 2 变为。 给定了
时间2:会员1被评级 4 然后离开。
时间 3:评分会员 2 1 给予。会员2的费率是 2 变为。 给定了
时间4:会员2费率 4 然后离开。

最低会员费率 它不能大于 5 ,因此最小值为 4 变为。 给定了
该示例满足子任务 1 和 2 的约束。


入力例2

4 2
2 3 1 3
2 4
1 7
3 8
5 6

出力例2

7

此示例满足子任务 1 的约束。


入力例3

6 4098
8 6 9 1 2 1
1 3
5 9
4 11
8 12
2 10
6 7

出力例3

2532

此示例满足子任务 3 的约束。

作者: 蓟