9170 - 买石榴
时间限制 : 1 秒
内存限制 : 128 MB
州庆期间，小轩来蒙自游玩，发现这里的石榴十分好吃，于是想带n个石榴回去给亲戚们尝尝鲜。他发现超市一共有 m 种包装的石榴，不同包装内的石榴数量有可能不同，价格也有可能不同。为了公平起见，小轩决定只买同一种包装的石榴。 由于超市不允许将石榴的包装拆开，因此小轩可能需要购买超过 n 个石榴才够给亲戚们都尝尝鲜。 现在小轩想知道，在超市每种包装的数量都足够的情况下，要买够至少n个石榴最少需要花费多少钱。
输入
第一行包含两个正整数n和m，表示需要的石榴数量和包装种数。 接下来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。
来源
蒙自市凤凰小学 boren.deng