SSOI要设计n道比赛试题，题目可以在m个算法专题中选择。由于算法专题有限，SSOI不得不重复选择一些算法专题。

  设计不同算法专题的试题所花的时间不同。具体地说，对于某个算法专题i，若SSOI计划一共设计x道试题，则完成该算法专题的试题总共需要花费Ai*x^Bi个单位时间（系数Ai和指数Bi均为正整数）。给定与每一个算法专题相对应的Ai和Bi的值，请帮助SSOI计算出如何选择试题的算法专题使得他可以花费最少的时间完成这n道试题。

第一行有两个用空格隔开的正整数n和m，分别代表需要设计的比赛试题和可供选择的算法专题数。

接下来m行，每行有两个用空格隔开的正整数。其中第i行的两个数分别代表与第i个算法专题相对应的时间系数Ai和指数Bi。

一行一个整数，比赛设计n道试题所需要耗费的最少时间。

对于30%的数据，n≤10,m≤5；

对于100%的数据，n≤200，m≤20，Ai≤100，Bi≤5。