J2 例题-5 远方的朋友

题目描述

佩奇进入了梦中一维世界，这个世界按照直线依次排列着 $10^{100}+1$ 个城堡，编号从 $0 -10^{100}$ 号。 佩奇最初有 $K$ 格体力（体力没有上限，每吃一个帮帮糖就可回复一格体力）。 她从第 $0$ 号城堡出发，只能向一个方向移动，并且每次只能移动一格。即从第 $i$ 个城堡走到第 $i+1$ 一个城堡，这样会消耗一格体力。 已知佩奇有 $N$ 个好朋友，居住在 $A_i$ 号城堡的朋友，如果他们相见了，会赠送 $B_i$ 个帮帮糖给佩奇。 请问，在朋友的帮助下，佩奇最远可以走到第几号城堡？

输入格式

共 $N+1$ 行： 第一行有两个整数 $N$ 和 $K$，表示佩奇的好友数量与她的初始体力值； 接下来 $N$ 行，每行两个整数 $A_i,B_i$，表示佩奇的朋友所在的城堡坐标与帮帮糖数量。

输出格式

一个整数，表示佩奇最后，可以到达的最远城堡编号。

样例输入1

2 4
3 1
5 10

样例输出1

15

样例1解析

佩奇从 $0$ 号城堡出发，初始体力为 $4$，消耗 $3$ 点体力，到达 $3$ 号城堡； 第一位朋友送给她 $1$ 个帮帮糖，她吃掉后体力回复到的 $2$ ，可到达 $5$ 号城堡； 第二位朋友送给她 $10$ 个帮帮糖，她吃掉后体力回复到的 $10$ ，可到达 $15$ 号城堡。

样例输入2

2 5
3 1
10 7

样例输出2

6

数据范围

$100 \%$ 的数据：$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$； 保证所有输入都是整数。