CON ĐƯỜNG ĐẸP

Để phục vụ cho việc hoàn thiện công trình thanh niên của Đoàn trường Đại học Công nghệ Thông tin và Truyền thông (ICTU), Đoàn trường có ý định mua \(n\) viên gạch kích thước \((1 \times 3)\) để lát đường đi từ quảng trường gần tòa nhà C1 vào phía công viên, đường đi có kích thước \((1 \times 3n)\). Trên bề mặt mỗi viên gạch có \(3\) ô vuông, mỗi ô vuông có thể trống hoặc chứa một chữ số từ \(0\) đến \(9\). Ví dụ, có \(4\) viên gạch [.15], [7..], [532], [..3] (dấu chấm để biểu thị cho ô trống).

Đoàn trường giao nhiệm vụ cho Liên chi Đoàn Khoa CNTT dùng hết toàn bộ gạch để lát kín đường đi. Liên chi Đoàn Khoa CNTT có thể lát các viên gạch theo bất kì thứ tự nào nhưng không được cưa các viên gạch ra và trên bề mặt phải chứa các ô vuông. Ví dụ, kết quả sau khi lát xong có thể là [532.15..37..] hoặc [7….3.15532],…

Sau khi lát xong, Đoàn trường ICTU sẽ chọn một hoặc nhiều ô vuông liên tiếp nhau sao cho các ô này đều có chứa chữ số, sau đó tính tổng \(S\) của các ô này. Độ đẹp của đường đi là giá trị lớn nhất của tổng \(S\). Ví dụ đường đi có dạng [532.15..37..] sẽ có độ đẹp là 10 (chọn 3 ô vuông đầu tiên); đường đi có dạng [7….3.15532] sẽ có độ đẹp là 16 (chọn 5 ô vuông cuối cùng). Đoàn trường yêu cầu Liên Chi Đoàn CNTT phải lát sao cho độ đẹp của đường đi là lớn nhất có thể.

Input:

• Dòng 1: Số nguyên dương \(n\).
• \(n\) dòng tiếp theo, mỗi dòng chứa một viên gạch để lát đường đi.

Output:

Ghi ra gồm một số duy nhất là độ đẹp lớn nhất.

Ví dụ:

Input:

4
.15
7..
532
..3

Output:

23

Giải thích:

Với cách lát [.155327….3] ta có độ đẹp của đường đi là 23 (chọn từ ô thứ 2 đến ô thứ 7).