‹ 上一题下一题 ›

j01001. 车辆加油未做

1000 ms 256 MB 测试点 5 J-26·查找与二分 J·算法自拟题二分

文件读写输入j01001.in输出j01001.out

题目描述

一辆车要从起点开到终点，全程 $L$ 公里。途中有 $n$ 个加油站，第 $i$ 个位于距起点 $x_{i}$ 公里处，最多能加 $g_{i}$ 升油。车每公里耗 $1$ 升，油箱容量为 $C$ （出发时满油），加油不能超过油箱剩余空间。求能到达终点的最小油箱容量 $C$ 。

输入格式

第一行两个整数 $L, n$ ；接下来 $n$ 行，每行两个整数 $x_{i}, g_{i}$ （ $x_{i}$ 严格递增）。

输出格式

一行一个整数。

样例

输入

10 2
3 5
7 5

输出

数据范围

$1 \leq n \leq 2 \times 1 0^{5}$
$1 \leq L \leq 1 0^{9}$
$0 < x_{i} < L$ 严格递增， $1 \leq g_{i} \leq 1 0^{9}$

输入

输出

答案