题目描述

Given a sequence of $n$ ordered pairs of positive integers $(a_i,b_i)$, you have to partition it into several contiguous parts. Let $p$ be the number of these parts, whose boundaries are $(l_1, r_1), (l_2, r_2), \cdots ,(l_p, r_p)$, which satisfy li = ri − 1 + 1, $l_i\leq r_i$, $l_1 = 1$,$r_p = n$. The parts themselves also satisfy the following estrictions:

1. For any two pairs $(a_p, b_p)$, $(a_q, b_q)$, where $(a_p, b_p)$ is belongs to the $t_p$ th part and $(a_q, b_q)$ the $t_q$ th part. If $t_p<t_q$, then $b_p>a_q$.

2. Let $m_i$ be the maximum $A\text{-component}$ of elements in the $i$ th part, say

   $m_i = \max\{a_{l_i}, \cdots ,a_{r_i}\},1\leq i \leq p$

   it is provided that

   $$\sum_{i=1}^p m_i\leq limit$$

   where $limit$ is a given integer.

Let $s_i$ be the sum of $B\text{-components}$ of elements in the $i$ th part. Now I want to minimize the value

$\max\{s_i:1\leq i \leq p\}$

Could you tell me the minimum?

输入格式

The input contains exactly one test case.

The first line of input contains two positive integers $n,limit$.

Then follow $n$ lines each contains a positive integers pair $(a,b)$. It's always guaranteed that $\max_{i=1}^n\{a_i\}\leq limit,\sum_{i=1}^n b_i\leq 2^{31}-1$。

输出格式

Output the minimum target value.

4 6
4 3
3 5
2 5
2 4

9

样例解释

An available assignment is the first two pairs are assigned into the first part and the last two pairs are assigned into the second part. Then $b_1>a_3,b_1>a_4,b_2>a_3,b_2>a_4,\max\{a_1,a_2\}+\max\{a_3,a_4\}\leq 6$, and minimum $\max\{b_1+b_2, b_3+b_4\}=9$.

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^4$，$limit\leq 2^{31}-1$。