Bộ Xếp Hình Đồng Đều · canuc80k0304

Có $m$ bộ xếp hình; bộ thứ $i$ gồm $f_{i}$ mảnh. Cần phát đúng một bộ cho mỗi trong $n$ học sinh, tức là chọn đúng $n$ bộ khác nhau. Độ lệch của một cách chọn là số mảnh lớn nhất trừ số mảnh nhỏ nhất trong các bộ đã chọn. Hãy tìm độ lệch nhỏ nhất.

Input

Dòng đầu chứa hai số nguyên $n$ và $m$ . Dòng thứ hai chứa $m$ số nguyên $f_{1}, f_{2}, \dots, f_{m}$ .

Output

In một số nguyên là độ lệch nhỏ nhất có thể đạt được khi chọn đúng $n$ bộ.

Constraints

$2 \leq n \leq m \leq 50$ .
$4 \leq f_{i} \leq 1000$ .

Scoring

Subtask $1$ ( $50$ điểm): $m \leq 15$ .
Subtask $2$ ( $50$ điểm): Theo đầy đủ các giới hạn đã nêu.

Example

Test 1

Input

5 9
14 4 8 9 10 15 6 7 20

Output

Giải thích: Chọn các bộ có $6, 7, 8, 9, 10$ mảnh thì độ lệch là $10 - 6 = 4$ . Không có năm bộ nào nằm trong một khoảng hẹp hơn.

Ý tưởng: Sau khi sắp xếp tăng dần, tồn tại một phương án tối ưu là một đoạn liên tiếp gồm n phần tử. Với cửa sổ bắt đầu tại l, độ lệch là a[l+n-1]-a[l].
Thuật toán: Sắp xếp m kích thước. Duyệt mọi cửa sổ liên tiếp dài n và lấy nhỏ nhất của hiệu hai đầu.
Chứng minh tính đúng đắn: Xét một cách chọn bất kỳ với phần tử nhỏ nhất ở vị trí l và lớn nhất ở vị trí r trong dãy đã sắp. Mọi phần tử giữa hai vị trí này đều nằm trong cùng khoảng giá trị, nên thay các phần tử được chọn bên trong bằng những phần tử nằm giữa không thể làm tăng độ lệch. Vì vậy có một cách chọn không tệ hơn dùng n phần tử liên tiếp. Thuật toán xét toàn bộ các cửa sổ như vậy nên chắc chắn gặp một phương án tối ưu và lấy đúng độ lệch nhỏ nhất.
Độ phức tạp: Thời gian O(m log m), bộ nhớ phụ O(log m) ngoài dãy.