小D最近热衷于洞穴探险,于是小D去了一趟超市购买了一些物资为下次洞穴探险做准备。
由于小D的背包容量有限,所以小D想在装满背包的前提下买价值尽量大的东西。
众所周知,这是一个01背包问题,由于小D精通ACM,所以这个问题已经被小D解决了。
但现在小D面临一个新的问题,由于小D的背包非常神奇,导致物品放入的顺序也会影响物品的价值。
具体地说,现在有 n 个物品,你可以选择放入若干个物品,一个都不放也行(虽然那样小D可能要饿死在洞穴中)。
每个物品有两个参数,系数 k 和重量 w,不妨设现在放入的物品的系数为 k,重量为 w,已经放入的物品的总重量为 s。
那么这个物品的价值为 k×w−s,求最大价值。
输入
第一行给出一个整数 T,表示有 T 组数据;
每组数据第一行给出一个整数 n;
接下来 n 行,每行给出 2 个整数 ki,wi;
1≤n≤5000,1≤ki,wi≤106
∑n≤20000
输出
输出一个整数,表示答案
输入示例
1
3
5 6
3 3
4 7
输出示例
55
示例说明
最优情况下要放入所有物品
第一次放入第二个物品,价值 3 * 3 - 0 = 9
第二次放入第一个物品,价值 5 * 6 - 3 = 27
第三次放入第三个物品,价值 4 * 7 - 9 = 19
总和为 55