Новое увлечение Колобка — рисование. Он решил купить k наборов карандашей. Каждый набор состоит из одного или нескольких карандашей. Каждый карандаш имеет положительную длину, которая выражается целым числом миллиметров.
В магазине продаются n наборов карандашей. После того, как Колобок купит ровно k наборов, он придёт домой и сложит все карандаши в одну коробку. Колобок очень обрадуется, если разница в длине между наибольшим и наименьшим карандашами в этой коробке будет минимальна.
Поэтому он просит вас помочь ему: выберите из n наборов карандашей ровно k так, чтобы разница между максимальным и минимальным среди всех купленных карандашей была как можно меньше.
Формат входного файла
В первой строке находятся два натуральных числа n, k (1 ≤ n ≤ 10
5 , 1 ≤ k ≤ n) — количество наборов карандашей, имеющихся в магазине, и количество наборов, необходимое Колобку. В каждой из следующих n строк находится ci (1 ≤ ci ≤ 2·10
5 ) — количество карандашей в наборе. Далее, в этой же строке, следуют ci натуральных чисел aij (1 ≤ a
ij ≤ 10
9 ) — длины карандашей в i-м наборе. Гарантируется, что сумма всех c
i не превосходит 2 · 10
5 .
Формат выходного файла
В единственной строке выведите наименьшую разницу между максимальным и минимальным купленными карандашами, которую можно достичь.
| Ввод |
Вывод |
3 2
3 1 3 4
3 5 1 2
1 4 |
3 |
5 3
3 2 1 3
2 4 1
3 4 2 4
4 3 2 3 3
2 5 6 |
3 |