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

[problemUrl]: https://atcoder.jp/contests/pakencamp-2020-day2/tasks/pakencamp_2020_day2_f 時は20XX年、パ研部室は室内で問題を解くとレートが $ 2 $ 倍になる機能を獲得していた。 しかし、超常現象と化したパ研部室であろうとも部員たちのレートに差があることはどうしようもなく、ある日このことを嘆いたパ研部長は部員たちのレートを平等に再分配することにした。 部長の計画が決行される日、パ研には $ N $ 人の部員が訪れる。 $ i $ 番目の部員はレート $ A_i $ であり、時刻 $ L_i $ にパ研部室に入り、時刻 $ R_i $ に部室を去る。複数の部員が同時刻に出たり入ったりすることはない。 部長は部員がパ研の出入口を通るとき、つまり部室に入るときと去るときに部員のレートから任意の**整数**を引いて、その分だけ自らのレートに足すことができる。 ただし、この操作のどの時点でも部員、部長のレートが負の値になってはならない。 部長が操作を行った時、部員 $ i $ のレートの遷移は以下のようになる。ここで、 $ E $ とは部長のレートである。 - 部室に入る前は $ A_i $ である。 - パ研部室に入る。部長に $ x\ (-E\ \leq\ x\ \leq\ A_i) $ 引かれる。部長、部員 $ i $ のレートはそれぞれ $ E+x,\ A_i-x $ になる。 - パ研部室で問題を解く。レートが $ 2 $ 倍になる。 - パ研部室を去る。部長にレートを $ y\ (-E'\ \leq\ y\ \leq\ A_i') $引かれる。部長、部員 $ i $ のレートはそれぞれ $ E'+y,\ A_i'-y $ になる。ここで、 $ E',A_i' $ というのは、部員 $ i $ が部室を去る時点での部長、部員 $ i $ のレートである。 計画開始から終了までの中で、部長のレート $ E $ が出入口での操作以外により増減することはない。 あなたの仕事は、部長がすべての操作を終えた時の「部長を除く部員のレートの最小値」の最大値を求めることだ。

入力は以下の形式で与えられる。 > $ 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\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ E\ \leq\ 10^9 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ 1\ \leq\ L_i\