题目描述

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

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

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

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

输入格式

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

第 $2$~$P+1$行：每行两个整数 $L_i$ 和 $C_i$ ( $0 \le L_i,C_i \le 2^{24}$ )。

输出格式

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

样例

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

5