Trên trục số OX có N điểm đón học sinh, được đánh số từ ~1~ đến ~N~. Trường học nằm tại điểm số ~N+1~.

Xe buýt bắt đầu hành trình từ điểm đón số 1 và di chuyển dọc theo trục OX đến trường học. Trên đường đi, xe buýt có thể dừng lại tại mỗi điểm đón để đón học sinh.

Tại mỗi điểm đón thứ ~i~:

• Có ~B_i~ học sinh đang chờ xe.
• Học sinh thứ ~j~ tại điểm này sẽ bắt đầu chờ xe từ thời điểm ~T_{i,j}~ (nghĩa là không thể đón học sinh đó sớm hơn thời điểm này).
• Thời gian để xe di chuyển từ điểm đón ~i~ sang điểm đón ~i+1~ là ~A_i~.

Xe buýt có sức chứa tối đa là M học sinh.

Tại mỗi điểm đón, xe buýt có thể:

• Dừng lại để đợi học sinh đến (nếu chưa đủ số lượng và còn chỗ).
• Hoặc tiếp tục di chuyển nếu không muốn đợi thêm.

Yêu cầu: Tính thời gian tối thiểu để xe buýt hoàn thành hành trình từ điểm 1 đến trường học, trong đó:

• Hoặc đã đón đủ M học sinh,
• Hoặc đã đón hết toàn bộ học sinh nếu tổng số học sinh ít hơn ~M~.

Gọi ~K~ là tổng số học sinh tại tất cả các điểm (tổng ~B_i~):

• Với mọi test:
  
  • ~T_{i,j} ≤ 10^9, A_i ≤ 10^9~
  • ~K ≤ 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