题目描述

农夫约翰正在为他的奶牛准备一顿美味的晚餐！在他的谷仓里，他有 $N$ 个干草捆 $(1 \le N \le 10^5)$ 。第 $i$ 个干草捆有一定的风味 $F_i(1 \le F_i \le 10^9)$ 和一定的辣度 $S_i(1 \le S_i \le 10^9)$ 。

这顿饭将由一道菜组成，是一个连续的区间，包含一个或多个连续的干草捆(农夫约翰不能改变干草捆的顺序)。这顿饭的总体的风味是这段区间里风味的总和。这顿饭的总体辣度是区间中所有草包的最大辣度。

农夫约翰想确定他的这道菜所能达到的最小辣度，但是这道菜的总风味必须至少为 $M(1 \le M \le 10^{18})$ 。

输入格式

第一行包含两个整数 $N$ 和 $M$ ，分别是干草包的数量和这顿饭必须有的最小风味之和。

接下来的 $N$ 行，每行两个整数描述这 $N$ 个草包，首先是风味 $F_i$，然后是辣度 $S_i$。

输出格式

请输出这道菜中在满足最低风味时的最低辣度。保证至少有一顿单道菜的饭能满足风味的要求。

输入输出样例 #1

输入 #1

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

输出 #1

9