Нове захоплення Степана#161

Нове захоплення Степана

1 секунда
512 мегабайтів
Середня

Нове захоплення Степана - малювання. Він вирішив купити наборів олівців. Кожен набір складається з одного або декількох олівців. Кожен олівець має додатну довжину, яка виражається цілим числом міліметрів.

У магазині продаються наборів олівців. Після того, як Степан купить рівно наборів, він прийде додому і складе всі олівці в одну коробку. Степан дуже зрадіє, якщо різниця в довжині між найбільшим і найменшим олівцями в цій коробці буде мінімальна.

Тому він просить вас допомогти йому: виберіть з наборів олівців рівно так, щоб різниця між максимальним і мінімальним серед всіх куплених олівців була якомога менша.

Вхідні дані

У першому рядку вхідного файлу знаходяться два натуральних числа N, K (1 \le N \le 10^{5}, 1 \le K \le N) - кількість наборів олівців, наявних в магазині, і кількість наборів, необхідних Степану.

У кожному з наступних рядків знаходиться C_{i} (1 \le C_{i} \le 2*10^{5}) - кількість олівців в наборі. Далі, в цьому ж рядку, слідують C_{i} натуральних чисел A_{ij} (1 \le A_{ij} \le 10^{9}) - довжини олівців в -му наборі.

Гарантується, що сума всіх C_{i} не перевищує 2*10^{5}.

Вихідні дані

У єдиному рядку вихідного файлу виведіть найменшу різницю між максимальним і мінімальним купленими олівцями, яку можна досягти.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Оцінювання

В даній задачі три підзадачі. Бали за кожну підзадачу нараховуються тільки якщо усі тести підзадачі пройдені.

Підзадача 1 (31 бал):

n \le 20, k > 1

Підзадача 2 (31 бал):

n \le 2000

Підзадача 3 (38 балів):

Без додаткових обмежень.