3015. 小高斯和小欧几里德(II)

单点时限: 2.0 sec

内存限制: 256 MB

小王子莫名奇妙的发了一通气,然后扔下好多编程作业,不做完不准回家吃饭。小高斯和他的好朋友小欧几里德不开心了,他们决定合作来完成这次作业,由小高斯写程序,小欧几里德调试,小高斯和小欧几里德都是学校的神牛,所以对于每道题目,都知道自己写或调试需要的时间,他们想尽快完成任务,想知道最少要花的时间。(假设小高斯和小欧几里德都有电脑)

输入格式

第 1 行:一个整数 T 为问题数。

对于每组测试数据:每组第一行包括一个整数 n,(1<=n<=100000),接下来有 n 行,每行包括小高斯写第 i 题的时间 (ai) 和小欧几里德调试的时间 (bi)。

输出格式

对每组输入,输出一行问题的编号(0 开始编号,格式:case #0: 等)然后输出最少要花的时间。

样例

Input
1
5
2 5
4 2
3 3
6 1
1 7
Output
case #0: 19

提示

Sample 的处理顺序:5 1 3 2 4

15 人解决,24 人已尝试。

17 份提交通过,共有 121 份提交。

6.0 EMB 奖励。

创建: 6 年,3 月前.

修改: 2 年,4 月前.

最后提交: 11 月前.

来源: 小高斯系列

题目标签