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é si tờ với các mệnh giá: c(i,1), c(i,2),…, c(i,si). 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
• 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à si , tiếp theo là các số c(i,1), c(i,2),…, c(i,si), 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.

Sample Input

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

Sample Output

9

Ràng buộc

Sub1: n<=100
Sub2: n<=10000