题目思路

考虑模拟，由于时间比较大，我们无法一个一个时间枚举。可以考虑使用带有时间的事件来模拟步骤的进行。

一个做蛋糕的事件由t, i, c表示，t表示这个开始这个事件的时间，i表示做的是蛋糕的第几个步骤，c表示这个事件的蛋糕数量。我们可以将所有的事件按照时间排序，然后按照时间顺序进行模拟。

初始状态便是由n / c[0]个事件，每个事件包含c[0]个蛋糕，时间依次为t[0], 2t[0], 3t[0], ...

然后将事件放入最小堆中模拟，每次根据第一位的时间来排序。由于步骤有一定的容量限制，我们还需要维护一下每个步骤目前正在进行的步骤事件，步骤事件用tim和num分别表示目前正在占用该步骤的蛋糕的结束时间和数量。初始的时候设定所有的步骤事件的时间为0，数量就为步骤的容量。

题目描述

小红很喜欢做蛋糕，做蛋糕有$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

说明

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