题目描述

你有n个部下，每个部下需要完成一项任务。第i个部下需要你花Bj分钟交代任务，然后他就会立刻独立地、无间断地执行Ji分钟后完成任务。你需要选择交代任务的顺序，使得所有任务尽早执行完毕（即最后一个执行完的任务应尽早结束）。注意，不能同时给两个部下交代任务，但部下们可以同时执行他们各自的任务。

输入格式

输入包含多组数据，每组数据的第一行为部下的个数N(1<=N<=1000);以下N行每行两个正整数B和J（1<=B<=10000,1<=J<=10000),即交待任务的时间和执行任务的时间。输入结束标志为N=0。

输出格式

对于每组数据，输出所有任务完成的最短时间。

3
2 5
3 2
2 1
3
3 3
4 4
5 5
0

Case 1: 8
Case 2: 15