9170 - 买石榴

州庆期间,小轩来蒙自游玩,发现这里的石榴十分好吃,于是想带n个石榴回去给亲戚们尝尝鲜。他发现超市一共有 m 种包装的石榴,不同包装内的石榴数量有可能不同,价格也有可能不同。为了公平起见,小轩决定只买同一种包装的石榴。 由于超市不允许将石榴的包装拆开,因此小轩可能需要购买超过 n 个石榴才够给亲戚们都尝尝鲜。 现在小轩想知道,在超市每种包装的数量都足够的情况下,要买够至少n个石榴最少需要花费多少钱。

输入

第一行包含两个正整数nm,表示需要的石榴数量和包装种数。 接下来m行,每行用 2 个正整数描述一种包装的石榴:其中第 1 个整数表示这种包装内石榴的数量x,第 2 个整数表示这种包装的价格y

输出

1 个整数,表示小轩最少需要花费的钱。

样例

输入

57 3                    
2 2
50 32
32 27

输出

54

输入

66 5                     
12 6
13 4
24 34
45 45
13 7

输出

24

提示

数据保证,2≤n,m≤100,1≤x,y≤200。

来源

用户上传

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题