Kolobok's new hobby — drawing. He decided to buy k sets of pencils. Each set consists of one or more pencils. Each pencil has a positive length, which is expressed as an integer number of millimeters.
The store sells n sets of pencils. After Kolobok buys exactly k sets, he will come home and put all the pencils in one box. Kolobok will be very happy if the difference in length between the largest and smallest pencils in this box is minimal.
Therefore, he asks you to help him: choose exactly k out of n sets of pencils so that the difference between the maximum and minimum among all purchased pencils is as small as possible.
Input file format
The first line contains two natural numbers n, k (1 ≤ n ≤ 10
5 , 1 ≤ k ≤ n) — the number of sets of pencils available in the store, and the number of sets needed by Kolobok. Each of the next n lines contains ci (1 ≤ ci ≤ 2·10
5 ) — the number of pencils in the set. Next, on the same line, follow ci natural numbers aij (1 ≤ a
ij ≤ 10
9 ) — lengths of pencils in the i-th set. It is guaranteed that the sum of all c
i does not exceed 2 · 10
5 .
Output file format
On a single line print the smallest difference between the maximum and minimum purchased pencils that can be reached.
|
Enter |
Output |
3 2
3 1 3 4
3 5 1 2
14 |
3 |
5 3
3 2 1 3
2 4 1
3 4 2 4
4 3 2 3 3
2 5 6
|
3 |