Cắt bảng

View as PDF

Submit solution


Points: 0.46 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 đề

image

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

Input

  • Dòng 1: Hai số nguyên dương ~M~ và ~N~ ~(1 \le M, N \le 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.

Output

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

Sample Input

2 3
1 2 3
3 1 2

Sample Output

435

Comments

Please read the guidelines before commenting.


There are no comments at the moment.