1159: 韩信点兵

内存限制:16 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:6 通过:1 通过率:16.667%

题目描述

韩信点兵,多多益善。

战前,萧何备军。韩信检阅,曰:“增1人?”。萧何答:“甚好”。韩信再曰:“使看齐?”。

萧何再答“甚好”。

输入格式

输入有多组(不超过100)测试实例。

每组测试实例第1行为1个正整数M1 ≤ M ≤ 100),表示接下来有M行士兵的信息。每行士兵信息为两个正整数H100 ≤ H ≤ 200)、N1 ≤ 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

数据范围与提示

“使看齐?”,指增加的这名士兵与其他每名士兵的身高差之和可否达到最小?