#P1019. 排考场

排考场

圣芙蕾雅学园的考场安排

期末考试临近,圣芙蕾雅学园学园长德丽莎·阿波卡利斯找来姬子老师和符华班长,一起为 NN 名女武神学员安排考场座位。学园里共有 MM 间教室,第 ii 间教室是一个 RiR_i 行 CiC_i 列的矩形座位区(每个座位至多坐一人)。

为了防止学员之间通过崩坏能“互相帮助”,德丽莎规定:在每间教室内,学员只会被安排在若干列上(同一列可以坐多行学员)。定义该教室的列间距为:

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

德丽莎希望所有教室的列间距中的最小值尽可能大,这样无论琪亚娜、芽衣还是布洛妮娅分到哪间教室,都能获得公平的考试环境。

请你帮助德丽莎求出这个最大可能的最小列间距。

Input

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

接下来 MM 行,每行包含两个整数 Ri,CiR_i, C_i。

数据范围:

1≤N≤1091 \le N \le 10^9,
1≤M≤1051 \le M \le 10^5,
1≤Ri,Ci≤1091 \le R_i, C_i \le 10^9,
∑i=1MRi<N\sum_{i=1}^M R_i < N,
∑i=1MRi×Ci≥N\sum_{i=1}^M R_i \times C_i \ge N。

Output

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

15 3
3 4
4 2
2 5
1

Notes

三间教室中,第一间教室列间距可以为 (2),第二间教室只使用一列故列间距视为无穷大,第三间教室列间距可以为 (1);所有教室列间距的最小值为 (1)。(排法不唯一)