题目描述

给定正整数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

本地修订说明

保留原目标和完整1e5/1e12/2e9规模，仅补n≥1、连续段必须非空，以及m<max(a)时明确输出-1。

根据用户授权整理。本题使用公开样例与独立自编训练数据，非官方原版评测数据。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：保留原目标和完整1e5/1e12/2e9规模，仅补n≥1、连续段必须非空，以及m<max(a)时明确输出-1。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1790。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共7个测试点，非原站或官方原始数据。总分100分。