题目描述

两个数组 A 和 B 均含有 N 个整数元素。现在给出一个整数 M，如果 A 中连续的一段区间 [i, j] 内的元素的和不小于 M，即 $(\sum_{k=i}^{j}A_k) ≥ M$，则称这个区间为“足够大区间”。对于任意的一个“足够大区间” A[i..j]，对应 B 的相同区间 B[i..j] 内的最大的元素被称作“足够大的数”，这个数即 $max(B_i,B_{i+1},...B_{j-1},B{j})$。

你的任务是，找到一个合适的“足够大区间”，使得“足够大的数”尽可能地小，并输出这个最小的“足够大的数”。

输入格式

第一行：两个整数 N, M ，以一个空格分隔。

接下来 N 行，每行两个整数 Ai, Bi，以一个空格分隔，依次表示 A、B 中的第 i 个元素。

输出格式

一个整数，表示最小的“足够大的数”。数据保证有解。

样例输入

5 10
4 8
6 9
3 5
4 6
3 7

样例输出

7

数据范围

40%的数据：$1 \le N \le 1000$

100%的数据：$1 \le N \le 10^5$，$1 \le M \le 10^{18}$，$1 \le A_i, B_i \le 10^9$