AT_pakencamp_2020_day2_f 来年も本選に20人送り込むので覚悟しておいてください

在20XX年，信息学部的研究室获得了一种超能力：在室内解题时，部员的评分（rate）会变成两倍。然而，即使是拥有超自然现象的研究室，部员之间的评分差异依旧存在。某一天，研究室的部长对这一现象感到不满，决定将部员的评分进行公平的再分配。 计划执行的当天，有 $ N $ 名部员来到了研究室。第 $ i $ 个部员的评分是 $ A_i $，他在时刻 $ L_i $ 进入研究室，并在时刻 $ R_i $ 离开。不同部员不会在同一时刻同时进入或离开。 部长在部员进出研究室时，可以从部员的评分中减去一个任意的**整数**，并将其加到自己的评分中。操作时必须保证无论何时，部员和部长的评分都不能为负数。 具体的操作如下： - 部员在进入研究室之前的评分是 $ A_i $。 - 进入研究室后，部长可以从部员的评分中减去 $ x $（满足 $ -E \leq x \leq A_i $），此时部长和部员的评分分别变为 $ E + x $ 和 $ A_i - x $。 - 在研究室内解题时，部员的评分会变成两倍。 - 离开研究室时，部长可以从部员的评分中再减去 $ y $（满足 $ -E' \leq y \leq A_i' $），此时部长和部员的评分分别变为 $ E' + y $ 和 $ A_i' - y $。这里 $ E' $ 和 $ A_i' $ 分别是部员离开时部长和部员的评分。 部长的评分 $ E $ 只会在部员进出时发生变化，其他时候保持不变。 你的任务是求出，所有操作结束后，部员评分的最小值的最大可能值。

输入的第一行包含两个整数 $ N $ 和 $ E $。 第二行包含 $ N $ 个整数 $ A_1, A_2, \ldots, A_N $。 接下来的 $ N $ 行，每行包含两个整数 $ L_i $ 和 $ R_i $，表示第 $ i $ 个部员的进入和离开时间。 翻译by_[QWQ_rua_QWQ](https://www.luogu.com.cn/user/1233838)

输出一个整数，表示部员评分的最小值的最大可能值。如果结果大于等于 $ 10^{12} $，则输出 `'inf'`。 #### 样例输入 #1 ``` 2 2 1 1 1 2 3 4 ``` #### 样例输出 #1 ``` 4 ``` #### 样例输入 #2 ``` 4 2 2 3 1 3 2 4 1 7 3 8 5 6 ``` #### 样例输出 #2 ``` 7 ``` #### 样例输入 #3 ``` 6 4098 8 6 9 1 2 1 1 3 5 9 4 11 8 12 2 10 6 7 ``` #### 样例输出 #3 ``` 2532 ```

###### 约束条件 - $ 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 $ - 小测试 3 (550分): 无其他额外约束 ##### 样例解释 #1 在这个例子中，部长可以采取以下步骤： - 时刻1：给部员1分配1个评分，部员1的评分变为2。 - 时刻2：部员1的评分变为4并离开。 - 时刻3：给部员2分配1个评分，部员2的评分变为2。 - 时刻4：部员2的评分变为4并离开。 部员的评分的最小值无法超过5，所以最终答案是4。此样例满足小测试1和2的约束条件。