Problem 1097 --刷题狂魔

1097: 刷题狂魔

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 30  Solved: 10
[Submit][Status][Web Board][Creator:]

Description

——” 请问宁成功的原因是什么?是努力吗?”

——” 不,是天分。”

这世上有两种可怕的人,一种是有天分的人,另一种是有天分且努力的人,恰好 ZHAN 就是第二种。

自从 ZHAN 加入 ACM 队以来,在每个夜深人静的夜晚,ZHAN 都在努力刷题。

——” 又是一个刷题的夜晚。”

ZHAN 挑选了 n 道题开始刷,由于 ZHAN 非常有天分,所以他可以不经思考直接知道每道题的题意和解法,所以他的工作只剩下写代码。因此,每道题在他眼里只有两个属性:代码量 ai(单位: 行) 和疲劳值 bi

ZHAN 需要同时面对这 n 道题。每一分钟的开始,所有未解决的题而使 ZHAN 的疲劳度增大,增大值为未解决的所有题的疲劳值之和。然后他要选择一个题写代码,对同一道题写代码的第 i 分钟能写这道题的 2i−1 行代码。如果某一分钟里他提前写完了代码,那么这一分钟剩下的时间他会仔细检查代码,而不会写其他题 (一分钟的时间只能被分配到一整道题,不可中途写其他题)。当一道题剩余代码量 ≤ 0 时,这道题将被解决,后续不再会对 ZHAN 造成疲劳度。当所有题被写完时,ZHAN 就可以休息了。

由于 ZHAN 在刷题过程中不休息,所以每一分钟产生的疲劳度将会累加。ZHAN 想使自己在刷题结束时的疲劳度最小,请你求出这个最小值。

Input

第一行包含一个整数 T(1 ≤ T ≤ 103),表示有 T 组测试数据。

接下来依次描述 T 组测试数据。对于每组测试数据:

第一行包含一个整数 n(1 ≤ n ≤ 105),表示题目的数量。

接下来 n 行,每行包含两个整数 ai, bi(1 ≤ ai, bi ≤ 105),表示第 i 道题的代码量和疲劳值。

保证所有组数据的 n 之和不超过 106.

Output

对于每组测试数据,输出一行一个整数,表示 ZHAN 在刷题结束时产生的疲劳度的最小值。

Sample Input

2
3
1 1
2 2
3 3
3
3 1
2 2
1 3

Sample Output

19
14

HINT

对于第一组样例,第 1 道题 ZHAN 要做 1 分钟,第 2、3 道题要做 2 分钟.

ZHAN 按照 3,2,1 的顺序做题.

在第 1 分钟开始时,ZHAN 增加 1+2+3 点疲劳度,这一分钟 ZHAN 写第 3 道题.

在第 2 分钟开始时,ZHAN 增加 1+2+3 点疲劳度,这一分钟 ZHAN 写第 3 道题,并将它写完了。

在第 3 分钟开始时,ZHAN 增加 1+2 点疲劳度,这一分钟 ZHAN 写第 2 道题.

在第 4 分钟开始时,ZHAN 增加 1+2 点疲劳度,这一分钟 ZHAN 写第 2 道题,并将它写完了。

在第 5 分钟开始时,ZHAN 增加 1 点疲劳度,这一分钟 ZHAN 写第 1 道题,并将它写完了。

ZHAN 产生的疲劳度之和为 19.

对于第二组样例,第 1、2 道题 ZHAN 要做 2 分钟,第 3 道题要做 1 分钟.

ZHAN 按照 3,2,1 的顺序做题.

在第 1 分钟开始时,ZHAN 增加 1+2+3 点疲劳度,这一分钟 ZHAN 写第 3 道题,并将它写完了。

在第 2 分钟开始时,ZHAN 增加 1+2 点疲劳度,这一分钟 ZHAN 写第 2 道题.

在第 3 分钟开始时,ZHAN 增加 1+2 点疲劳度,这一分钟 ZHAN 写第 2 道题,并将它写完了。

在第 4 分钟开始时,ZHAN 增加 1 点疲劳度,这一分钟 ZHAN 写第 1 道题.

在第 5 分钟开始时,ZHAN 增加 1 点疲劳度,这一分钟 ZHAN 写第 1 道题,并将它写完了。

ZHAN 产生的疲劳度之和为 14.

Source

[Submit][Status]