该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一块矩形蛋糕通过卡车运往一家餐厅。在前往目的地的途中，卡车撞到了一个坑洞，导致蛋糕碎裂成 $N$ 个完美的矩形碎片，每个碎片的宽度为 $w_i$，长度为 $l_i$，其中 $1 \leq i \leq N$。

到达目的地后，对损坏进行了评估，顾客决定订购一个尺寸相同的替代蛋糕。不幸的是，原始订单填写不完整，只知道蛋糕的宽度 $W$。餐厅请求你帮助找出蛋糕的长度 $L$。幸运的是，所有碎裂的蛋糕碎片都被保留了下来。

输入格式

输入包含以下整数：

• 第一行：蛋糕的宽度 $W$；
• 第二行：碎裂的碎片数量 $N$；
• 接下来的 $N$ 行：每行包含每个碎片的宽度 $w_i$ 和长度 $l_i$。

输出格式

输出应为整数 $L$。

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

6

提示

数据范围

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