序列划分 - ROJ

给定正整数 $m$ 以及长度为 $n$ 的序列对 $(a_i,b_i)$ ，你需要将它分为连续的若干段，满足以下2个条件： ① 若 $ia_j$ 。 ② 每一段的 $a$ 的最大值之和 $≤m$ 。在此基础上，你需要最小化每一段的 $b$ 的和的最大值。

第一行两个正整数 $n，m$ ，接下来 $n$ 行每行两个正整数 $a_i，b_i$ 。

一行一个整数表示答案。

【数据规模】

数据编号	$n≤$	特殊性质1	特殊性质2
$1$	$1000$	无	无
$2$
$3$	$100000$	$a_i$ 在 $[1,10^9]$ 内均匀随机	$min(b_i)>max(a_i)$
$4$	$a[i]>a[i+1]$
$5$	无
$6$	$a_i$ 在 $[1,10^9]$ 内均匀随机	$b_i$ 在 $[1,10^9]$ 内均匀随机
$7$	无
$8$	$a[i]>a[i+1]$
$9$	无
$10$

对于100%的数据， $n≤100000，m≤10^{12}，1≤a_i，b_i≤2×10^9$ 。