#1787. 收购魔法石

收购魔法石

题目描述

由于魔法石的巨大消耗,魔法学院需要购买不同等级的魔法石,有高等级也有低等级, 每个等级有一定的价钱。每一次买一种等级的魔法石,必须多买10\red{10}个。为了节约用钱,魔 法学院会采取如下的方法:比如,需要买5\red{5}1\red{1}等级低的魔法石,每颗10\red{10}元,100\red{100}2\red{2}等 级高的魔法石,每颗20\red{20}元。如果每个等级都买到需要: (5+10)×10+(100+10)×20=\red{(5+ 10)\times 10+(100+10)\times 20=} 2350\red{2350}元。但如果不买低等级的魔法石而换买高等级的,则用钱为(5+100+10)×20=\red{(5+ 100+ 10)\times 20 =} 2300\red{2 300}元,这样就省钱了!

要求输出买所有的魔法石,可以把低等级的换买高等级的,但不能把高等级的换买低等 级的,需要花费的最少钱数。

输入格式

第一行包含一个数字N,\red{N,}即有N\red{N}组测试数据。每组测试数据的行数由c(1\red{c (1≤}c\red{c≤}100)\red{100)}来 决定,C\red{C}行中的每一行都包含 两个数字ai\red{ai}pi,\red{pi,}第一个数字表示需要的魔法石数(1\red{(1≤}ai\red{ai≤} 1000),\red{1000),}第二个数字表示该类魔法石的价值(1\red{(1≤}pi\red{pi≤}1000)\red{1000)}。魔法石的品质由低至高严格按 顺序给出。所有数字均为整数。

输出格式

每组测试数据输出一行,每行均为最少钱数。

样例

输入样例

2
100 1
100 2

输出样例

330