荣耀之战

题目描述

小 $A$ 是一名游戏玩家，他正在玩一款叫做“荣耀之战”的游戏。在这个游戏中，他需要通过完成任务来提升自己的等级。

游戏地图上有 $N$ 个排成一排的装备，每个装备都标注好了经验值和危险值，第 $i$ 个装备的经验值为 $V_{i}$ 危险值为 $D_{i}$。

小 $A$ 接到了一个任务，他需要在这 $N$ 个装备中，选取连续的若干个装备，并使得这些装备的经验值总和不小于 $K$（$≥K$）。同时要使得这些装备的最大的危险值尽可能的小。

请编程计算出，满足题意的方案中，最大的危险值最小是多少？

输入

第 $1$ 行读入 $2$ 个整数 $N,K$。

接下来 $N$ 行，每行读入 $2$ 个整数 $V_{i},D_{i}$ ，分别表示每个装备的经验值和危险值。

输出

输出满足题意的最大危险值最小是多少。

样例

输入数据1

5 10
4 10
6 15
3 5
4 9
3 6

输出数据1

9

输入数据2

6 15
3 9
8 6
5 8
4 1
1 6
9 9

输出数据2

8

说明

样例 $1$ 说明

共有 $5$ 个装备，要求选取连续的若干个装备，使得装备的经验值总和 $≥10$ 。

分析可知，选择最后 $3$ 个装备，经验值总和$=3+4+3=10$，最大危险值$=max(5,9,6)=9$，该方案为最大危险值最小的方案，因此，最大危险值最小为 $9$ 。

数据范围

对于 $100$% 的数据，满足 $1≤N≤10^{5}$，$1≤Vi,Di≤10^{9}$，$1≤K≤10^{18}$ 。