Anh nông dân John có ~N~ chuồng bò nằm rải rác khắp nông trang của mình, mỗi chuồng bò có ~M~ con bò. Hằng ngày, anh John đều cho mỗi con bò ăn một số lượng cỏ nhất định. Để tiết kiệm thời gian chăm sóc các con bò do phải đi lại giữa nhiều chuồng bò, anh John muốn gộp các chuồng bò lại thành một chuồng. Khi tiến hành gộp các chuồng bò, anh phải chọn ~2~ chuồng, gộp chúng lại với nhau thành ~1~ chuồng; rồi tiếp tục chọn ~2~ chuồng, gộp chúng lại với nhau thành ~1~ chuồng; cứ tiếp tục làm như vậy cho đến khi chỉ còn lại một chuồng. Anh John biết các con bò ở ~2~ chuồng chỉ chịu ở chung với nhau nếu số lượng cỏ mỗi ngày của con bò được cho ăn nhiều nhất ở ~2~ chuồng bằng nhau và các con bò ở trong cùng một chuồng cũng hay ganh tỵ nhau. Vì vậy, để làm các con bò vui vẻ trong việc gộp chuồng, anh sẽ tăng thêm cỏ cho mỗi con bò ở cùng chuồng một lượng như nhau trước khi tiến hành gộp các chuồng lại.

Yêu cầu

Hãy giúp anh nông dân John tính tổng lượng cỏ ít nhất phải tăng lên trong một ngày để gộp các chuồng bò lại làm một theo cách mô tả và thỏa các điều kiện nêu ra ở trên.

Dữ liệu vào

Gồm nhiều dòng:

Dòng thứ nhất chứa số nguyên ~N~, là số chuồng bò (~1 \leq N \leq 2 \times 10^5~).

Mỗi dòng trong ~N~ dòng tiếp theo mô tả một chuồng bò. Một chuồng bò được mô tả bắt đầu với số nguyên ~M~ là số con bò trong chuồng (~1 \leq M \leq 2 \times 10^5~), tiếp theo là ~M~ số nguyên tương ứng với số lượng cỏ hằng ngày dành cho mỗi con bò trong chuồng. Số lượng cỏ là số nguyên không vượt quá ~10^9~.

Các số trên một dòng cách nhau ít nhất một dấu cách.

Kết quả ra

Xuất ra màn hình một số nguyên, là tổng lượng cỏ ít nhất phải tăng lên trong một ngày để gộp các chuồng bò lại làm một theo cách mô tả và thỏa các điều kiện nêu ra ở trên.

Sample Input

3
2 3 4
2 2 1
3 1 1 1

Sample Output

13

Giải thích: Một cách tốt nhất để gộp các chuồng bò là: Đầu tiên, tăng lượng cỏ ở chuồng thứ hai thêm ~2~, gộp chuồng thứ nhất và chuồng thứ hai. Bây giờ, nông trại của anh nông dân John có ~2~ chuồng bò với lượng cỏ hằng ngày dành cho các con bò ở hai chuồng là ~[3, 4, 4, 3]~ và ~[1, 1, 1]~. Để gộp ~2~ chuồng bò này lại thì tăng lượng cỏ ở chuồng thứ hai thêm ~3~. Kết quả tổng lượng cỏ tăng thêm là ~2+2+3+3+3=13~.