問題文

時は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 が出入口での操作以外により増減することはない。

あなたの仕事は、部長がすべての操作を終えた時の「部長を除く部員のレートの最小値」の最大値を求めることだ。

制約

• 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点): 追加の制約はない。

入力例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の制約を満たす。