Một xe buýt của công ty có nhiệm vụ đón nhân viên đến trụ sở làm việc. Trên hành trình xe buýt sẽ tiếp nhận nhân viên đứng chờ ở các điểm hẹn nếu như xe còn chỗ trống. Xe buýt có thể sẽ đỗ lại để chờ những công nhân còn chưa kịp đến điểm hẹn. Cho biết thời điểm mà mỗi nhân viên đến điểm hẹn của mình và thời gian cần thiết để xe buýt di chuyển từ một điểm hẹn đến điểm hẹn tiếp theo. Giả thiết rằng xe buýt đến điểm hẹn đầu tiên tại thời điểm ~0~, thời gian xếp khách lên xe được coi là bằng ~0~.

Yêu cầu

Hãy xác định khoảng thời gian ngắn nhất để xe buýt có thể chở một số lượng nhiều nhất các nhân viên đến trụ sở làm việc.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~, ~m~ theo thứ tự là số điểm hẹn và số chỗ ngồi của xe bus ~(1≤n≤200000, 1≤m≤2000)~.
• Dòng thứ i trong số ~n~ dòng tiếp theo chứa số nguyên ~t_i~ là thời gian cần thiết để xe buýt di chuyển từ điểm hẹn ~i~ đến điểm hẹn ~i+1~ (điểm hẹn thứ ~n+1~ sẽ là trụ sở làm việc của công ty), số nguyên dương ~k_i~ là số lượng nhân viên đến điểm hẹn ~i~ và tiếp đến là ~k_i~ số nguyên là các thời điểm đến điểm hẹn của ~k_i~ nhân viên.

Biết rằng, tổng số lượng nhân viên không vượt quá ~200000~, và thời điểm đến điểm hẹn của các nhân viên là số nguyên không âm không vượt quá ~10^5~.

Output

Một dòng duy nhất là khoảng thời gian ngắn nhất tìm được.

Sample Input

3 5
1 2 0 1
1 1 2
1 4 0 2 3 4

Sample Output

4