1611: [ECUST2018新生赛]铺地板

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:36 通过:9

题目描述

小花梨要给家里铺地板啦,小花梨的家比较特别,可以看成n∗n的正方形。
它买了n∗n块地板,这些地板有m种不同的颜色,第ii种颜色的地板有ai块,所有的地板都是1∗1的正方形。
小花梨希望最终铺成的地板的每一行是完全一样的。它想知道自己买来的地板最多可以铺多少行。

输入格式

第一行一个整数T,表示有T组数据,对于每组数据:
第一行为整数n和m,含义如上
接下来一行有m个整数ai,表示第i种颜色的地板数目
输入保证ai之和等于n∗n
(1≤T≤10,1≤n,m≤50000,1≤ai≤n∗n)

输出格式

对于每一组数据,输出"Case x: ans "(不含引号)
x表示第x组测试数据,从1开始编号,ans表示最多可以铺好的行数

输入样例 复制

2
3 4
3 3 2 1
2 4
1 1 1 1

输出样例 复制

Case 1: 2
Case 2: 1