Bắt đầu từ ngày hôm nay, mỗi ngày mẹ sẽ đưa cho bé một số tờ tiền để nuôi heo. Cụ thể, ngày thứ \(i\) mẹ sẽ đưa cho bé \(s_i\) tờ với các mệnh giá: \(c(i,1), c(i,2),…, c(i,s_i)\). Bé sẽ lựa chọn (hoặc không chọn) một tờ trong số các tờ mẹ đưa để lì xì cho heo với điều kiện: tờ tiền lựa chọn của những ngày sau có mệnh giá không nhỏ hơn tờ tiền đã lựa chọn của những ngày trước.

Yêu cầu: Hãy giúp bé lựa chọn tờ tiền để heo mau lớn nhất. (chọn nhiều tiền nhất)

Input

• Dòng 1: chứa số \(n\) là số ngày

• \(n\) Dòng sau, mỗi dòng mô tả các tờ tiền mà mẹ cho. Dòng thứ \(i\) mô tả ngày thứ \(i\), số đầu tiên của dòng là \( s_i\) , tiếp theo là các số \(c(i,1), c(i,2),…, c(i,s_i)\), mệnh giá của mỗi tờ ≤ 10000.

Output

• Gồm một dòng chứa tổng số tiền lớn nhất có thể chọn được để nuôi heo.

Ràng buộc

• Sub1: n ≤ 100

• Sub2: n ≤ 10000

Sample Input

6 
3 1 1 1 
2 2 3 
2 2 3 
1 1 
2 2 2 
2 2 2

Sample Output

9