题目描述

奶牛们想把水从池塘运输到牛棚里，池塘和牛棚相距D个单位。它们有P根水管，每根水管由2个整数来描述：水管长度Li，最大流量Ci。

水管可以依次连接构成一条运输管道（下水道？），那么这条运输管道的流量就是构成这条管道的所有水管中最小的一个流量。

但是，要让水从池塘通过运输管道流到牛棚里，管道的长度必须恰好等于池塘和牛棚的距离（也就是说，水管长度Li之和为D）！

现在只要求构造一条运输管道，求其最大流量。

输入格式

第1行：两个整数，D(7<=D<=100,000)和P(1<=P<=350)；

第2..P+1行：每行两个整数Li和Ci(0<=Li,Ci<=2^24)。

输出格式

一行仅一个整数，表示最大流量。

样例

input

7 6
4 5
3 6
2 7
1 4
6 7
1 5

output

5

限制与提示

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$