Giải bài trực tuyến

Quân có một tấm bảng hình chữ nhật gồm M dòng và N cột, mỗi ô nhỏ của bảng là một ô vuông có cạnh là 1 đơn vị, và sẽ chứa một chữ số từ 0 đến 9. Anh chuẩn bị cắt tấm bảng thành các mảnh rời nhau. Mỗi mảnh sẽ theo chiều ngang hoặc dọc, chứa một hoặc nhiều ô nhỏ. Một trong hai chiều của mảnh phải là 1 đơn vị.

Với mảnh dọc, ghép các chữ số từ trên xuống dưới, Quân sẽ được một số.
Với mảnh ngang, ghép các chữ số từ trái sang phải, Quân cũng được một số.
Các số này có thể có số 0 ở đầu.

Bạn hãy tìm cách chia để Quân có được tổng các số trên các mảnh là lớn nhất.

Hãy xem hình sau để hiểu hơn đề

Ví dụ như ở cách chia trên, tổng có được là
493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879.

Dữ liệu

• Dòng 1: Hai số nguyên dương M và N (1 ≤ M, N ≤ 4).
• M dòng tiếp theo, mỗi dòng gồm N chữ số cách nhau bởi khoảng trắng, thể hiện bảng chữ nhật của Quân.

Kết quả

• Tổng lớn nhất tìm được.

Ví dụ

Input:
2 3
1 2 3
3 1 2

Ouput:
435

(Trong lúc thi, sẽ chấm trước 4 test (bao gồm test ví dụ)).