{"code":"21thtbc2","name":"Bài tập (THT B&C TQ 2021)","description":"Hồng đã soạn được $n$ bài tập Tin học, bài thứ ݅$i(1 \\le i \\le ݊n)$ có độ khó là số nguyên dương $c_i$. Hồng được cô giáo yêu cầu gửi $m$ bài tập lên hệ thống luyện tập trực tuyến để tập huấn cho một nhóm các em học sinh khóa dưới. Nếu $m < n$, khi đó, Hồng phải loại bỏ $n - m$ bài tập, ngược lại nếu $m > n$ thì Hồng phải soạn thêm $m - n$ bài tập với độ khó là số nguyên dương. Khi đưa lên hệ thống $m$ bài tập, Hồng sẽ sắp xếp các bài theo độ khó tăng dần, gọi $d$ là chênh lệch độ khó lớn nhất của hai bài tập liên tiếp. Hồng mong muốn giá trị $d$ nhỏ nhất có thể. \r\n\r\n**Yêu cầu:** Cho $n$ bài tập với độ khó là ܿ$c_1, c_2, ..., c_n$ và số $m$, hãy tìm giá trị $d$ nhỏ nhất.\r\n\r\n

Input

\r\n\r\nVào từ thiết bị vào chuẩn:\r\n \r\n- Dòng đầu gồm hai số nguyên dương ݊$n, m (2 \\le m, n \\le 10^5; m \\ne n)$; \r\n- Dòng thứ hai gồm ݊ số nguyên dương $c_1, c_2, ..., c_n$ $(c_i \\le 10^9, 1 \\le i \\le n)$.\r\n\r\n

Output

\r\n\r\n- Ghi ra thiết bị ra chuẩn gồm một dòng chứa một số nguyên $d$ tìm được.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 5 4\r\n 8 5 9 10 10\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 1\r\n ```\r\n \r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3 4\r\n 8 6 9\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 1\r\n ```","points":500.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}