#P1336. 最佳课题选择
最佳课题选择
题目描述
Matrix67 要在下个月交给老师 篇论文,论文的内容可以从 个课题中选择。由于课题数有限,Matrix67 不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说,对于某个课题 ,若 Matrix67 计划一共写 篇论文,则完成该课题的论文总共需要花费 个单位时间。给定与每一个课题相对应的 和 的值,请帮助 Matrix67 计算出如何选择论文的课题使得他可以花费最少的时间完成这 篇论文。
输入格式
第一行两个整数 和 ,分别代表需要完成的论文数和可供选择的课题数。
接下来 行每行两个整数。其中,第 行的两个数分别代表与第 个课题相对应的时间系数 和指数 。
输出格式
输出完成 篇论文所需要耗费的最少时间。
10 3
2 1
1 2
2 1
19
提示
样例说明
篇论文选择课题一, 篇论文选择课题三,剩下一篇论文选择课题二,总耗时为 。可以证明,不存在更优的方案使耗时小于 。
数据规模与约定
对于 的数据,。
对于 的数据,,,,。