题目描述

给定正整数m与长度n的正整数序列对(a_i,b_i)，把整个序列分成连续、非空的若干段，满足：

1. 对任意i<j，只要i与j不在同一段，就必须有b_i>a_j（严格大于）。
2. 每段a_i的最大值相加不超过m。

在所有满足条件的方案中，最小化“各段b_i之和的最大值”。

输入

第一行n,m，随后n行a_i,b_i。

输出

最小的最大段b和。若没有满足预算的合法分段，输出-1。

数据范围

1≤n≤100000，1≤m≤10^12，1≤a_i,b_i≤2×10^9。段和与答案可能超过32位。

输入样例

4 6
4 3
3 5
2 5
2 4

输出样例

9