UVA11729 Commando War

> _我们在树林里等待命令，前线的消息却始终没有传来 到傍晚，枪声已经遥远 啊，我们悄悄地穿过阴影，轻轻地从树间溜走 在薄雾中穿过他们的防线，跪着爬过田野 而我所能看到的 是空中的火焰，发出红光，映衬着随风飘散的烟雾_ 有一场对你的国家来说形势并不乐观的战争。现在是时候行动了。你有一支突击队可以调遣，并计划对附近一个重要的敌军营地进行伏击。你的队伍里有 $N$ 名士兵。在你总体的计划中，每个士兵都有独特的职责，你不希望任何士兵知道其他人的计划，以便每个人都能专注于自己的任务。为了达成这一点，你分别向每个士兵简要说明任务，并在他们被派往战场之前单独进行简报。你知道每个士兵完成任务需要一定的时间。你也很清楚给每个士兵进行简报需要多长时间。由于你急于尽快完成整个行动，你需要找到一个简报顺序，使所有士兵完成任务的总时间最少。你可以假设，没有士兵的计划依赖于其他士兵的任务。换句话说，一旦士兵开始执行任务，他可以不间断地完成任务。

输入文件中会有多个测试用例。每个测试用例以一个整数 $N$（$1 \le N \le 1000$）开始，表示士兵的数量。接下来 $N$ 行，每行描述一个士兵，并给出两个整数 $B$（$1 \le B \le 10000$）和 $J$（$1 \le J \le 10000$）。表示向该士兵简报所需的时间是 $B$ 秒，该士兵完成任务所需的时间是 $J$ 秒。输入由 $N = 0$ 表示结束，这个测试用例不应被处理。

对于每个测试用例，按 $\texttt{Case }X\texttt{: }Y$ 的格式打印一行，其中 $X$ 是测试用例编号，$Y$ 是从第一次简报开始到所有任务完成所经过的总秒数。 --- Translated by User 735713.