Đón xe buýt

Không biết cụm từ "Làng đại học" có từ khi nào, bắt nguồn từ đâu, nhưng suốt những năm tháng đại học, chúng tôi đã thuộc nó làu làu, xem như một mật ngữ riêng của giới sinh viên TPHCM.

Những con đường rợp hoa giấy dẫn vào trường, bờ Hồ Đá và tán cây hoa chuông nhuộm vàng cả một vùng trời… đã trở thành chốn hẹn hò bí mật của bao cặp đôi ở độ tuổi đang yêu.

Nói không ngoa khi đã là sinh viên TPHCM, chẳng ai không biết đến "Làng đại học". Mật ngữ ấy như phần ký ức tươi đẹp theo suốt năm tháng đầu tiên đứa học sinh tỉnh lẻ bước chân lên Sài Gòn nhưng sợ sự xô bồ, tấp nập nơi thành phố. Ấy vậy, sau này ra trường, đi làm, lập gia đình, nhưng mỗi lần nhìn lại, bao kỷ niệm thanh xuân bỗng chốc ùa về trong veo.

Ấn tượng của riêng tôi đối với Làng đại học chính là những chuyến xe buýt, khi bạn chỉ cần đứng đợi vài phút là sẽ có một chuyến xe đưa bạn tới trường chỉ với 3 nghìn đồng.

Trong thế giới tương lai, những điểm đón xe buýt của Làng đại học được xếp thành một đường thẳng trên. Có \(n\) điểm đón xe buýt, và điểm thứ \(n + 1\) là trường Đại học Công nghệ thông tin (UIT). Xe buýt bắt đầu tại điểm đón thứ \(1\), đi lần lượt tới các điểm tiếp theo và kết thúc chuyến ở trường Đại học Công nghệ thông tin. Tại điểm đón thứ \(i\), sẽ có \(B_{i}\) sinh viên đón xe buýt ở đây, sinh viên thứ \(j\) trong \(B_{i}\) sinh viên này sẽ đợi xe buýt từ thời điểm \(T_{i, j}\). Từ điểm đón thứ \(i\) đi sang điểm đón thứ \(i + 1\), xe buýt sẽ mất \(A_{i}\) đơn vị thời gian để di chuyển.

Xe buýt này có \(M\) ghế ngồi, tới mỗi điểm đón xe buýt sẽ chọn dừng lại để chờ sinh viên (nếu còn chỗ ngồi) hoặc đi tiếp (hoặc chờ một chút rồi đi tiếp). Hỏi thời gian tối thiểu để xe buýt đi hết một lượt từ đầu tới cuối là bao nhiêu ? (lượt đi này phải đón đủ \(M\) học sinh hoặc đã đón hết tất cả học sinh).

Input

Dòng đầu tiên là hai số nguyên dương \(n\) và \(m\), lần lượt là số điểm đón và số ghế trên xe buýt. \((1 \leq n, m \leq 2 \times 10^5)\).

\(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên không âm \(A_{i}, B_{i}\). Tiếp sau đó là \(B_{i}\) số nguyên không âm \(T_{i, 1}, T_{i, 2}, ..., T_{i, b_{i}}\) \((A_{i}, T_{i, j} \leq 10^9)\).

Dữ liệu đảm bảo tổng số sinh viên chờ xe buýt không vượt quá \(2 \times 10^5\).

Output

Thời gian tối thiểu để đón \(M\) học sinh (hoặc đón tất cả các học sinh).

Example

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

12

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

15

Scoring

\begin itemize

• Có \(25\%\) số điểm có \(n, m \leq 20\) và tối đa \(20\) sinh viên chờ xe buýt.

• Có \(25\%\) số điểm có \(n, m \leq 2000\) và tổng số sinh viên chờ xe buýt không vượt quá \(2000\).

• Có \(25\%\) số điểm có \(A_{i}, T_{i, j} \leq 100, n \leq 1000\).

• \(25\%\) số điểm còn lại không có ràng buộc gì thêm.

\end itemize