CF 337A - Puzzles

The end of the school year is near and Ms. Manana, the teacher, will soon have to say goodbye to a yet another class. She decided to prepare a goodbye present for her n students and give each of them a jigsaw puzzle (which, as wikipedia states, is a tiling puzzle that requires the assembly of numerous small, often oddly shaped, interlocking and tessellating pieces).

The shop assistant told the teacher that there are m puzzles in the shop, but they might differ in difficulty and size. Specifically, the first jigsaw puzzle consists of f1 pieces, the second one consists of f2 pieces and so on.

Ms. Manana doesn't want to upset the children, so she decided that the difference between the numbers of pieces in her presents must be as small as possible. Let A be the number of pieces in the largest puzzle that the teacher buys and B be the number of pieces in the smallest such puzzle. She wants to choose such n puzzles that A - B is minimum possible. Help the teacher and find the least possible value of A - B.

Input

The first line contains space-separated integers n and m (2 ≤ n ≤ m ≤ 50). The second line contains m space-separated integers f1, f2, ..., fm (4 ≤ fi ≤ 1000) — the quantities of pieces in the puzzles sold in the shop.

Output

Print a single integer — the least possible difference the teacher can obtain.

Examples

input

Copy

4 6
10 12 10 7 5 22

output

Copy

5

Note

Sample 1. The class has 4 students. The shop sells 6 puzzles. If Ms. Manana buys the first four puzzles consisting of 10, 12, 10 and 7 pieces correspondingly, then the difference between the sizes of the largest and the smallest puzzle will be equal to 5. It is impossible to obtain a smaller difference. Note that the teacher can also buy puzzles 1, 3, 4 and 5 to obtain the difference 5.

-------------------------------

学年即将结束，老师马纳娜女士很快就要告别另一个班级了。 她决定为她的 n 个学生准备一份告别礼物，并给他们每个人一个拼图游戏（正如维基百科所述，这是一种平铺拼图，需要组装许多小的、通常形状奇怪的、互锁和镶嵌的碎片）。

店员告诉老师，店里有m个拼图，但难度和大小可能有所不同。 具体来说，第一个拼图游戏由 f1 块组成，第二个拼图由 f2 块组成，依此类推。

马纳纳女士不想让孩子们不高兴，所以她决定礼物的件数差异必须尽可能小。 设 A 为老师购买的最大拼图的片数，B 为最小的拼图的片数。 她想选择这样的 n 个谜题，使得 A - B 的可能性最小。 帮助老师找出A - B的最小可能值。

输入

第一行包含空格分隔的整数 n 和 m (2 ≤ n ≤ m ≤ 50)。 第二行包含 m 个空格分隔的整数 f1, f2, ..., fm (4 ≤ fi ≤ 1000) — 商店中出售的拼图的块数。

输出

打印一个整数——教师可以获得的最小可能差异。

-------------------------------------

排序，然后求区间的最大值即可。下面是代码：