配点: 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 的约束。