思路

选出最大的所有小于等于总价格的优惠价格即可。

代码

C++

题目描述

小红在点外卖，他在小红学算法这个公众号领了m张不可重叠使用的满减券，问点这份外卖最少花多少钱。

输入描述

第一行是两个整数$n,m$，表示外卖总价格为n，有m张优惠券。

接下来m行，每行两个整数a,b，表示满a减b。

保证 $1 \leq n \leq 100000$, $1 \leq m \leq 200$, $1 \leq b \leq a \leq 100000$, $n \leq a$

输出描述

一行，一个整数，表示最少花的钱

样例

输入

10 3
30 50
20 30
5 5

输出

5