Sáp nhập công ty

Một tập đoàn gồm $n$ công ty. Để dễ quản lý, chủ tập đoàn quyết định sáp nhập tất cả các công ty thành một. Theo luật, mỗi lần chỉ được sáp nhập hai công ty, vì vậy người ta sẽ liên tiếp chọn ra hai công ty rồi gộp lại, cho đến khi chỉ còn duy nhất một công ty.

Tuy nhiên, cơ quan chống độc quyền chỉ cho phép sáp nhập hai công ty nếu mức lương cao nhất của hai công ty đó bằng nhau.

Để thoả mãn điều kiện trên, chủ tập đoàn có thể điều chỉnh lương trong các công ty trước khi sáp nhập, nhưng phải tuân theo hai quy tắc của công đoàn:

• Chỉ được tăng lương, không được giảm.
• Trong một lần điều chỉnh, tất cả nhân viên của cùng một công ty phải được tăng cùng một số tiền như nhau.

Hãy tìm tổng số tiền tăng lương ít nhất (tính trên tất cả các nhân viên) để có thể sáp nhập tất cả công ty thành một.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số công ty của tập đoàn.
• Trong $n$ dòng tiếp theo, dòng thứ $i$ mô tả công ty thứ $i$: bắt đầu bằng số nguyên $m_i$ — số nhân viên của công ty, tiếp theo là $m_i$ số nguyên dương — mức lương của từng nhân viên.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng số tiền tăng lương ít nhất.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le m_i\le 2·{10}^5$
• $1\le$ mức lương $\le {10}^9$
• Tổng $m_i$ trên toàn bộ các công ty không vượt quá $2·{10}^5$.

Ví dụ