题目描述

贝贝需要为 $N$ 名学生安排考场座位。现有 $M$ 间教室，第 $i$ 间教室是一个 $R_i$ 行 $C_i$ 列的矩形座位区（每个座位至多坐一人）。

在每间教室内，学生只会被安排在若干列上（同一列可以坐多行学生）。定义该教室的列间距为：

• 如果该教室只使用了一列，则列间距视为无穷大；
• 否则，列间距定义为任意两列相邻被使用列之间所间隔的未使用列数量中的最小值。

贝贝希望安排所有学生（每个学生一个座位），使得所有教室的列间距中的最小值尽可能大。你需要输出这个最大可能的最小列间距。

输入格式

第一行包含两个整数 $N, M$。

接下来 $M$ 行，每行包含两个整数 $R_i, C_i$。

保证 $1 \le N \le 10^9$，$1 \le M \le 10^5$，$1 \le R_i, C_i \le 10^9$，$\sum_{i=1}^{M} R_i < N$，$\sum_{i=1}^{M} R_i \times C_i \ge N$。

输出格式

输出一个整数，表示列间距最小值的最大可能取值。

样例

输入

15 3
3 4
4 2
2 5

输出

1

说明

样例 1 中，三间教室如下图所示，数字代表学生，第 1 间教室列间距为 2，第 2 间教室列间距视为无穷大，第 3 间教室列间距为 1，三间教室的列间距最小值为 1。（排法不唯一）