题目描述

塔子哥很喜欢做蛋糕，做蛋糕有$k$个步骤，第$i$个步骤有$c_i$个人可以完成，每个人只能做同时做一个蛋糕，并且只会那一个步骤，也就是最多可 以同时有$c_i$个蛋糕在进行第$i$个步骤。一个蛋糕的第$i$个步骤需要$t_i$的时间。小红想要做n个蛋糕，问最少需要多少时间可以完成。

输入描述

第一行两个整数 n,k，表示蛋糕数量和步骤数量。

接下来k行，每行两个整数$c_i, t_i$，表示第i个步骤的人数和时间。

$1 <= n, k ,c_i <= 1000$

$1 <= t <= 10^9$

输出描述

输出一个整数，表示最少需要的时间.

样例

输入

3 3
2 1
2 2
3 1

输出

6

说明

第一秒，两个蛋糕完成步骤一。
第二秒，一个蛋糕完成步骤一，两个蛋糕完成步骤二的第一秒。
第三秒，两个蛋糕完成步骤二。一个蛋糕等待步骤二。
第四秒，两个蛋糕完成步骤三。一个蛋糕完成步骤二的第一秒。
第五秒，一个蛋糕完成步骤二。
第六秒，一个蛋糕完成步骤三。