Haybale Feast

题目描述

农夫约翰正在为他的奶牛准备一顿美味的餐点！在他的谷仓里，他有 $N$ 个干草堆（$1 \le N \le 100,000$）。第 $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$，然后是辣度 $S$。

输出格式

请输出满足最小风味要求的单道菜餐点的最小辣度。 保证总存在至少一种满足风味要求的单道菜餐点。

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

9

提示

题目致谢：Christopher Chang 和 Allen Chen

标签: USACO|2017|Gold

来源

USACO|2017|Gold