题目描述(ID:12049)
标题: 写作文
标签: 动态规划
详情:
淘淘要在下个月交给老师n篇作文,作文的内容可以从m个题目中选择。由于题目数有限,淘淘不得不重复选择一些题目。完成不同题目的作文所花的时间不同。具体地说,对于某个题目i,若淘淘计划一共写x篇作文,则完成该题目的作文总共需要花费Ai*x^Bi个单位时间(系数Ai和指数Bi均为正整数)。给定与每一个题目相对应的Ai和Bi的值,请帮助淘淘计算出如何选择作文的题目使得他可以花费最少的时间完成这n篇作文。
输入格式:
第一行有两个用空格隔开的正整数n和m,分别代表需要完成的作文数和可供选择的题目数。
以下m行每行有两个用空格隔开的正整数。其中,第i行的两个数分别代表与第i个题目相对应的时间系数Ai和指数Bi。
对于30%的数据,n<=10,m<=5;
对于100%的数据,n<=200,m<=20,Ai<=100,Bi<=5。
输出格式:
输出完成n篇作文所需要耗费的最少时间。
样例:

输入

10 3
2 1
1 2
2 1

输出

19
登录并解答