Có ~N~ điểm đón học sinh nằm trên trục OX được đánh số từ 1 đến ~N~ và trường học ở điểm ~N+1~. Xe bus xuất phát tại điểm đón thứ 1. Điểm thứ ~i~ có ~B_i~ học sinh đợi xe bus, học sinh thứ ~j~ sẽ đợi từ thời điểm ~T_{i, j}~ và tốn thời gian là ~A_i~ để đi từ điểm ~i~ đến điểm ~i+1~. Xe bus có tất cả ~M~ chỗ ngồi tại mỗi điểm đón xe có thể đợi thêm người đến (nếu còn chỗ) hoặc đi luôn. Hỏi thời gian tối thiểu để đi hết 1 lượt là bao nhiêu ?. Tức là yếu cầu bạn tính thời gian tối thiểu để đón ~M~ học sinh hoặc tất cả học sinh.

Với mọi sub ~A_i, T_{i, j} <= 10^9~, gọi ~K~ là tổng số học sinh ở ~N~ bến.

Với mọi sub ~K <= 200000~

Sub1: ~N, M, K <= 2000~

Sub2: ~A_i, T_{i, j} <= 100, N <= 1000~

Sub3: ~N, M <= 200000~

Input

Dòng 1: 2 số nguyên ~N, M <= 200000~ số điểm đón và số ghế

~N~ dòng tiếp gồm ~A_i, B_i, T_{i, 1}, ..., T_{i, B_i}~ thời gian di chuyển từ bến i đến bến i+1, số học sinh đợi ở bến ~B_i~ và thời gian các bạn học sinh đến bến.

Output

Thời gian tối thiểu để bus đón học sinh

Sample Input 1

4 5
2 2 1 3
2 3 1 2 3
4 2 12 19
3 2 10 7

Sample Output 1

12

Sample Input 2

3 6
2 2 1 2
4 3 4 8 9
4 3 11 8 9

Sample Output 2

15