F. 全能猫娘的烦恼
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

在哈尔冰的比赛之后，小M 变成了猫娘。

某个周末在听完计拔基地启动仪式后，她顺手解决了车南大学OJ的问题。

于是，小M 是全能猫娘的消息终于瞒不住了。

各种各样的任务以各种各样的理由加入了 小M 的 TodoList。

为了高效的完成任务，小M 将这个周末的时间划分成了 $$$N$$$ 段。

在这 $$$N$$$ 段时间中 小M 需要完成 $$$M$$$ 项任务，每一项任务有一个耗时 $$$T_i$$$ 和一个 Deadline $$$S_i$$$ (需要恰在 $$$S_i$$$ 时刻或者在 $$$S_i$$$ 时刻之前完成)。

当然，小M 必须在对应的 Deadline 之前完成这项任务。另外，小M 是单线程猫娘，所以她做一项工作会一直做到完成为止。

猫娘当然是喜欢睡懒觉的，她想让你帮她算一算，在 Deadline 的压迫下，她最晚能在什么时候起床。

Input

第 $$$1$$$ 行 $$$2$$$ 个正整数 $$$N,M(1\le N\le 10^7;1\le M\le10^5)$$$，表示时间段的数量和任务数量。

第 $$$1+i$$$ 行 $$$2$$$ 个正整数 $$$T_i,S_i(1\le T_i\le10^5, 1\le S_i\le N)$$$，表示第 $$$i$$$ 个任务的耗时和 Deadline。

Output

第 $$$1$$$ 行一个整数 $$$ans$$$，表示 小M 最晚在 $$$ans$$$ 时刻起床干活可以顺利完成任务。

特别的，如果即使 小M 周末不睡觉 (在 0 时刻便起床开始干活) 也无法顺利在对应的 Deadline 前完成所有任务，那么请输出 -1。

Examples
Input
99 4
3 5
8 14
5 20
1 16
Output
2
Input
520 6
1 7
3 6
2 19
2 11
4 23
4 16
Output
3
Input
1314 1
16 7
Output
-1