Нове захоплення Степана - малювання. Він вирішив купити наборів олівців. Кожен набір складається з одного або декількох олівців. Кожен олівець має додатну довжину, яка виражається цілим числом міліметрів.
У магазині продаються наборів олівців. Після того, як Степан купить рівно наборів, він прийде додому і складе всі олівці в одну коробку. Степан дуже зрадіє, якщо різниця в довжині між найбільшим і найменшим олівцями в цій коробці буде мінімальна.
Тому він просить вас допомогти йому: виберіть з наборів олівців рівно так, щоб різниця між максимальним і мінімальним серед всіх куплених олівців була якомога менша.
У першому рядку вхідного файлу знаходяться два натуральних числа 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
Приклад 2
В даній задачі три підзадачі. Бали за кожну підзадачу нараховуються тільки якщо усі тести підзадачі пройдені.
Підзадача 1 (31 бал):
n \le 20, k > 1
Підзадача 2 (31 бал):
n \le 2000
Підзадача 3 (38 балів):
Без додаткових обмежень.