小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