PIG - Con heo đất
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

“Mẹ mua cho con heo đất, mẹ mua cho con heo đất í a í a, ngày hôm nay em vui lắm, cầm heo trên tay em ngắm, í à í a, làm sao cho heo mau lớn làm sao cho heo mau lớn í à í a. Heo không đòi ăn cơm, heo không đòi ăn cám, heo chỉ cần em bé trên tay ầu ơ, em không thèm mua kem, em không thèm mua bánh, em để dành cho heo, em lì xì heo đất 200 mỗi ngày. Này heo ơi! ngoan nhé! í a! này heo con ơi mau lớn í a”

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ứ mẹ sẽ đưa cho bé si tờ với các mệnh giá: ci,1, ci,2, ... ci,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

Input

- Dòng 1: chứa số 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ố  
ci,1, ci,2, ... ci,si. (si<=50; ci,j<=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.

Ví dụ

Input

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

Output

9

Giới hạn:

Subtask1: n<=100
Subtask2: n<=10000


Nguồn: 3D '1819

Back to Top