问题 C: 村庄旅行
内存限制:1024 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:122
解决:16
题目描述
小K想在$10^{100}+1$个村庄之间旅行,村庄编号为$0$到$10^{100}$。
第$i$个村庄只能从第$i-1$个村庄消耗$1$点体力到达。
同时,有$N$个补给点,在第$A_i$个村庄会回复$B_i$点体力。
假设小K初始在第$0$个村庄,初始体力为$K$,且体力不存在上限,小K最多能到达哪个村庄。
第$i$个村庄只能从第$i-1$个村庄消耗$1$点体力到达。
同时,有$N$个补给点,在第$A_i$个村庄会回复$B_i$点体力。
假设小K初始在第$0$个村庄,初始体力为$K$,且体力不存在上限,小K最多能到达哪个村庄。
输入
$N$ $K$
$A_1$ $B_1$
:
$A_N$ $B_N$
数据范围
$1 \leq N \leq 2 \times 10^5$
$1 \leq K \leq 10^9$
$1 \leq A_i \leq 10^{18}$
$1 \leq B_i \leq 10^9$
输入全是整数
$A_1$ $B_1$
:
$A_N$ $B_N$
$1 \leq N \leq 2 \times 10^5$
$1 \leq K \leq 10^9$
$1 \leq A_i \leq 10^{18}$
$1 \leq B_i \leq 10^9$
输入全是整数
输出
小K最多能到达的村庄编号
样例输入 复制
2 3
2 1
5 10
样例输出 复制
4