一块矩形蛋糕在通过卡车运往餐厅的途中，卡车撞上了一个坑洼，导致蛋糕碎成了 $N$ 块完美的矩形碎片，其宽度为 $w_i$，长度为 $l_i$，其中 $1 \leqslant i \leqslant N$。

到达目的地后，工作人员评估了损坏情况，客户决定订购一个尺寸相同的替换蛋糕。不幸的是，原始订单填写不完整，只知道蛋糕的宽度 $W$。餐厅请求你帮忙找出蛋糕的长度 $L$。幸运的是，所有破碎的蛋糕碎片都被保留了下来。

输入格式

输入包含以下整数： 第一行包含蛋糕的宽度 $W$； 第二行包含碎片数量 $N$； * 接下来的 $N$ 行，每行包含每个碎片的宽度 $w_i$ 和长度 $l_i$。

数据范围

• $1 \leqslant N \leqslant 5\,000\,000$；
• $1 \leqslant W, L \leqslant 10\,000$；
• 对于每个 $1 \leqslant i \leqslant N$，$1 \leqslant w_i, l_i \leqslant 10\,000$。

输出格式

输出应为一个整数 $L$。

样例

样例输入 1

4
7
2 3
1 4
1 2
1 2
2 2
2 2
2 1

样例输出 1

6