Олимпиадный тренинг

Задача . Карандаши


Задача

Темы: Структуры данных
Новое увлечение Колобка — рисование. Он решил купить k наборов карандашей. Каждый набор состоит из одного или нескольких карандашей. Каждый карандаш имеет положительную длину, которая выражается целым числом миллиметров.

В магазине продаются n наборов карандашей. После того, как Колобок купит ровно k наборов, он придёт домой и сложит все карандаши в одну коробку. Колобок очень обрадуется, если разница в длине между наибольшим и наименьшим карандашами в этой коробке будет минимальна.

Поэтому он просит вас помочь ему: выберите из n наборов карандашей ровно k так, чтобы разница между максимальным и минимальным среди всех купленных карандашей была как можно меньше.

Формат входного файла
В первой строке находятся два натуральных числа n, k (1 ≤ n ≤ 105 , 1 ≤ k ≤ n) — количество наборов карандашей, имеющихся в магазине, и количество наборов, необходимое Колобку. В каждой из следующих n строк находится ci (1 ≤ ci ≤ 2·105 ) — количество карандашей в наборе. Далее, в этой же строке, следуют ci натуральных чисел aij (1 ≤ aij ≤ 109 ) — длины карандашей в i-м наборе. Гарантируется, что сумма всех ci не превосходит 2 · 105 .

Формат выходного файла
В единственной строке выведите наименьшую разницу между максимальным и минимальным купленными карандашами, которую можно достичь.
 
Ввод Вывод
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

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w646
Комментарий учителя