题目描述
给定n种不同种类的珍珠,每种珍珠对应着一个单价和一个购买量,要求我们以最少的钱买到我们所需的同样购买总量的珍珠,而且保证珍珠的品质不能下降(即可以用价格高的珍珠替换价格低的珍珠),任意购买一种价格为pi数量为ni的珍珠需要支付(ni+10)*pi。求购买所需购买总量的珍珠的最小花费。
例如,10元的珍珠需要5颗,20元珍珠需要100颗。这通常会花费:(5 + 10)* 10 +(100 + 10)* 20 = 2350元,购买20元的总量为105的珍珠只需花费:(5 + 100 + 10)* 20 = 2300元,所以最小花费为2300元。
输入描述
第一行包含一个整数,表示测试用例的数量(不超过100)。
每个测试用例都以整数c(1 <= c <= 100)开头。然后,后面有c行,每行有两个数字ai和pi,ai表示我们所需的该类珍珠的数量(1 <= ai <= 1000),pi表示该类珍珠的价格(1 <= pi <= 1000)。
珍珠的价格按升序给出。
输出描述
对于每个测试用例,输出一行,包含一个数字,表示购买所需珍珠总购买量的最低价格。
样例输入
2
2
100 1
100 2
3
1 10
1 11
100 12
样例输出
330
1344
提示