4.汪星人的广场舞

【问题描述】 汪星人为响应“全民健身”的号召，正在举办一次大型的广场舞比赛，汪星的 m 个地 区（编号为 1 到 m）都派了一个代表队参加。由于各地区的的人口基数和积极性不同，每个 地区参加的人数有所差异，其中第 i 个地区参赛队的人数为 ai。 为了呈现广场舞壮观的场面，组织方决定所有参赛队在一个有 n 行若干列（列不够时 可以不断增加）的广场上排好队后同时跳舞。排队的具体方案如下： （1）每个参赛队根据地区编号大小依次从第 1 列的第 1 行开始排队，当第 1 列排满时 排第 2 列，依次下去，列数可以根据实际需要不断增加，直到所有的参赛队排完为止。 （2）排在同一列的参赛队之间至少要空一个位置的间距。为保证总体的整齐程度，每列的最前面和最后面不允许有空的位置（最后一列的最后一个参赛队之后可以留空位置）。 （3）每个地区的参赛队必须排在同一列中，且同一参赛队队员之间不可以有空位置。 如下图所示是 6 个参赛队排 10 行（即 n=10）时的排队情况（每个地区参赛队的人数依 次为 3,2,1,4,4,2，分别用不同的颜色表示不同的参赛队）。左右两个排队情况都满足组织方的 排队要求，但在图 a 中，所有参赛队之间空位置间距的最大值为 3，出现在第 2 个参赛队和 第 3 个参赛队之间，而在图 b 中任意两个参赛队之间的空位置间距都没有超过 2，所以组织 方认为图 b 的排队方案更加整齐美观。 同时，组织方认为下面几种排队方案都是不符合要求的： 请编程计算满足组织方排队要求的最大空位置间距的最小值，从而帮助组织方选择最整 齐美观排队方案。 【输入格式】 输入共 2 行。 第 1 行输入两个整数 n 和 m，分别表示排队时的行数和参加的队伍数（即地区数）。 第 2 行 m 个正整数 ai(1≤i≤m)，依次表示第 i 个参赛队的人数。 【输出格式】 输出 1 行一个整数，表示最大空位置间距的最小值。 【输入输出样例】 dance.in dance.out 10 6 3 2 1 4 4 2 2

【样例解释】 排队方案如本题图所示。 【数据范围约定】 测试点编号 n m ai(1≤i≤n) 1～6 3≤n≤102 2≤m≤102 1≤ai≤（n-1）/2 (即保证每一列中至 少可以排两个队伍)