问题描述

一个简单的背包问题dp

找不出状态转移方程

描述

一大堆期末考试来袭，草滩小王子被迫去上自习了。

除了自习，草滩小王子还想到了n件可以做的事，n件事可以选一些去做，

这些事会花费一定的时间并且必须一次完成不停止（本题中时间的最小单位为1秒）

并且可以提高（降低）草滩小王子自习的效率（神奇的是效率的提升是累加的），

草滩小王子一开始的效率只有1。

草滩小王子可以在任意时刻开始自习任意时间（效率不会因此降低），假设当前的效率为?ki?，

这段时间?ti内获得的收获?si=ti×ki?。

现在草滩小王子共有t秒的时间，该如何分配时间获得最大的自习收获呢。

输入

第一行是一个整数T(T<=10)，代表测试数据的组数。 对于每组测试数据： 第一行含两个个整数?t(0≤t≤1000),n(1≤n≤10000)?接下来n行，第行包括2个整数a,b(0≤a≤100,0≤b≤30)。?a代表第i件事所花的时间,b代表第i件事所提升的效率

输出

对于每组测试数据，输出一行，表示草滩小王子能够获得的最大收获

解决方案

输入
1
20 3
10 5
6 2
5 4

输出
75

hint
小王子花了5秒钟做完第3件事，然后花15秒钟去自习

解决方案二：

一个简单的背包问题