题目描述

小蓝要在自己的生日宴会上将 $n$ 包糖果分给 $m$ 个小朋友。每包糖果都要分出去，每个小朋友至少要分一包，也可以分多包。

小蓝已经提前将糖果准备好了，为了在宴会当天能把糖果分得更平均一些，小蓝要先计算好分配方案。

小蓝将糖果从 $1$ 到 $n$ 编号, 第 $i$ 包糖果重 $w_{i}$ 。小朋友从 $1$ 到 $m$ 编号。每个小朋友只能分到编号连续的糖果。小蓝想了很久没想出合适的分配方案使得每个小朋友分到的糖果差不多重。因此需要你帮他一起想办法。为了更好的分配糖果，他可以再买一些糖果，让某一些编号的糖果有两份。当某个编号的糖果有两份时，一个小朋友最多只能分其中的一份。

请找一个方案，使得小朋友分到的糖果的最大重量和最小重量的差最小，请输出这个差。

例如，小蓝现在有 5 包糖果, 重量分别为 $6,1,2,7,9$，如果小蓝要分给两个小朋友，则他可以将所有糖果再买一份，两个小朋友都分到 $1$ 至 $5$ 包糖果，重量都是 $25$, 差为 $0$。

再如，小蓝现在有 $5$ 包糖果, 重量分别为 $6,1,2,7,9$，如果小蓝要分给三个小朋友，则他可以将第 $3$ 包糖果再买一份，第一个小朋友分 $1$ 至 $3$ 包，第二个小朋友分 $3$ 至 $4$ 包，第三个小朋友分第 $5$ 包，每个小朋友分到的重量都是 $9$，差为 $0$。

再如, 小蓝现在有 5 包糖果, 重量分别为 $6,1,2,7,9$, 如果小蓝要分给四个小朋友，则他可以将第 $3$ 包和第 $5$ 包糖果再买一份, 仍然可以每个小朋友分到的重量都是 $9$，差为 $0$。

再如, 小蓝现在有 $5$ 包糖果, 重量分别为 $6,1,2,7,9$, 如果小蓝要分给五个小朋友, 则他可以将第 $4$ 包和第 $5$ 包糖果再买一份, 第一个小朋友分第 $1$ 至 $2$ 包重量为 $7$ , 第二个小朋友分第 $3$ 至 $4$ 包重量为 $9$, 第三个小朋友分第 $4$ 包重 量为 $7$, 第四个和第五个小朋友都分第 $5$ 包重量为 $9$。差为 $2$。

输入格式

输入第一行包含两个整数 $n$ 和 $m$, 分别表示糖果包数和小朋友数量。

第二行包含 $n$ 个整数 $w_{1}, w_{2}, \cdots, w_{n}$, 表示每包糖果的重量。

输出格式

输出一个整数, 表示在最优情况下小朋友分到的糖果的最大重量和最小重量的差。

5 2
6 1 2 7 9

0

5 5
6 1 2 7 9

2

提示

对于 $30 \%$ 的评测用例, $1 \leq n \leq 10,1 \leq m \leq 10,1 \leq w_{i} \leq 10$;

对于 $60 \%$ 的评测用例, $1 \leq n \leq 30,1 \leq m \leq 20,1 \leq w_{i} \leq 30$;

对于所有评测用例, $1 \leq n \leq 100,1 \leq m \leq 50,1 \leq w_{i} \leq 100$ 。在评测数据 中, $w_{i}$ 随机生成, 在某个区间均匀分布。

蓝桥杯 2021 第一轮省赛 A 组 J 题。