29090번 - Карандаши 다국어

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

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

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

В первой строке находятся два натуральных числа $n$, $k$ ($1 \le n \le 10^5, 1 \le k \le n$) --- количество наборов карандашей, имеющихся в магазине, и количество наборов, необходимое Колобку.

В каждой из следующих $n$ строк находится $c_i$ ($1 \le c_i \le 2 \cdot 10^5$) --- количество карандашей в наборе. Далее, в этой же строке, следуют $c_i$ натуральных чисел $a_{ij}$ ($1 \le a_{ij} \le 10^9$) --- длины карандашей в $i$-м наборе.

Гарантируется, что сумма всех $c_i$ не превосходит $2 \cdot 10^5$.

В единственной строке выведите наименьшую разницу между максимальным и минимальным купленными карандашами, которую можно достичь.