韩信点兵,多多益善。
战前,萧何备军。韩信检阅,曰:“增1人?”。萧何答:“甚好”。韩信再曰:“使看齐?”。
萧何再答“甚好”。
输入有多组(不超过100)测试实例。
每组测试实例第1行为1个正整数M(1 ≤ M ≤ 100),表示接下来有M行士兵的信息。每行士兵信息为两个正整数H(100 ≤ H ≤ 200)、N(1 ≤ N < 1000),分别表示士兵身高和其对应的士兵人数。
输入结束将由一行M=0的测试实例表示,不应处理此测试实例。
每组测试实例输出一行,格式为:“Case i: sum”,其中i是测试实例的编号(从1开始),sum为一个正整数,即增加的这名士兵与其他每名士兵的身高差之和,该和满足:是所有可能的和当中最小的和。
2
160 1
170 1
4
160 1
165 1
170 1
180 2
0
Case 1: 10
Case 2: 35
“使看齐?”,指增加的这名士兵与其他每名士兵的身高差之和可否达到最小?