A9100. Puzzles
编程题
普及/提高-
知识点
题目描述
学年即将结束，Manana 老师很快就要和她的又一届学生告别了。她决定为班上的 $n$ 名学生准备告别礼物，给每名学生一盒拼图。
商店的售货员告诉老师，商店里有 $m$ 盒拼图，但这些拼图的难度和大小可能不同。具体来说，第一盒拼图由 $f_1$ 块组成，第二盒拼图由 $f_2$ 块组成，依此类推。
Manana 老师不想让孩子们感到失望，因此她希望作为礼物的拼图块数之间的差异尽可能小。设她所购买的拼图中，块数最多的一盒有 $A$ 块，块数最少的一盒有 $B$ 块。她希望选择 $n$ 盒拼图，使 $A-B$ 尽可能小。
请帮助老师求出 $A-B$ 的最小可能值。
商店的售货员告诉老师，商店里有 $m$ 盒拼图，但这些拼图的难度和大小可能不同。具体来说，第一盒拼图由 $f_1$ 块组成，第二盒拼图由 $f_2$ 块组成，依此类推。
Manana 老师不想让孩子们感到失望，因此她希望作为礼物的拼图块数之间的差异尽可能小。设她所购买的拼图中，块数最多的一盒有 $A$ 块，块数最少的一盒有 $B$ 块。她希望选择 $n$ 盒拼图，使 $A-B$ 尽可能小。
请帮助老师求出 $A-B$ 的最小可能值。
输入格式
第一行包含两个用空格分隔的整数 $n$ 和 $m$。
第二行包含 $m$ 个用空格分隔的整数 $f_1,f_2,\ldots,f_m$，表示商店中出售的各盒拼图所包含的拼图块数。
第二行包含 $m$ 个用空格分隔的整数 $f_1,f_2,\ldots,f_m$，表示商店中出售的各盒拼图所包含的拼图块数。
输出格式
输出一个整数，表示老师能够得到的最小差值。
输入输出样例
输入 #1
4 6 10 12 10 7 5 22
输出 #1
5
说明/提示
### 样例 1 解释
班上有 $4$ 名学生，商店里出售 $6$ 盒拼图。如果 Manana 老师购买前四盒拼图，它们分别包含 $10$、$12$、$10$ 和 $7$ 块，那么其中最大块数与最小块数之差为 $5$。无法得到更小的差值。
老师也可以购买第 $1$、$3$、$4$ 和第 $5$ 盒拼图，同样得到差值 $5$。
### 数据范围
对于所有数据，满足：
- $2 \le n \le m \le 50$；
- $4 \le f_i \le 1000$；
- 时间限制为 $1$ 秒；
- 空间限制为 $256$ MB。
班上有 $4$ 名学生，商店里出售 $6$ 盒拼图。如果 Manana 老师购买前四盒拼图，它们分别包含 $10$、$12$、$10$ 和 $7$ 块，那么其中最大块数与最小块数之差为 $5$。无法得到更小的差值。
老师也可以购买第 $1$、$3$、$4$ 和第 $5$ 盒拼图，同样得到差值 $5$。
### 数据范围
对于所有数据，满足：
- $2 \le n \le m \le 50$；
- $4 \le f_i \le 1000$；
- 时间限制为 $1$ 秒；
- 空间限制为 $256$ MB。