NOIP '08 P3 - Message Passing - DMOJ: Modern Online Judge

NOIP '08 P3 - Message Passing

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem type

X and Y are good friends and classmates, and they always have endless topics to talk about together. In a quality development activity, the students in the class arranged to make a matrix with $m$ ~m~ rows and $n$ ~n~ columns, and X and Y were arranged at both ends of the diagonal of the matrix, so they could not talk directly. Fortunately, they can communicate by passing notes. The note will be passed to each other through many classmates. X sits in the upper left corner of the matrix with coordinates $(1,1)$ ~(1,1)~, and Y sits in the lower right corner of the matrix with coordinates $(m,n)$ ~(m,n)~. The note passed from X to Y can only be passed down or to the right, and the note passed from Y to X can only be passed up or left.

During the activity, X hopes to pass a note to Y, and at the same time hopes that Y will reply to him. Every student in the class can pass it on for them, but only once, that is to say, if this person helps when X passes the note to Y, then he will not help when Y passes it to X, and same in reverse.

There is one more thing to pay attention to. The kindness of each student in the class who is willing to help is high or low (note: the degree of kindness of X and Y is not defined, and it is represented by 0 when inputting). Kindnesses are given by natural numbers from $0-100$ ~0-100~, with larger meaning better. X and Y hope to find students with high levels of kindness as much as possible to help pass the note, that is, to find two transmission paths back and forth, so that the degree of kindnesses of the students on these two paths is only the maximum. Now, please help X and Y find such two paths.

Input Specification

Line 1 has two integers $m$ ~m~ and $n$ ~n~ separated by a space, which means that there are $m$ ~m~ rows and $n$ ~n~ columns in the class ( $1\leq m, n\leq 50$ ~1\leq m, n\leq 50~).

The next $m$ ~m~ rows are an $m \times n$ ~m \times n~ matrix. The integers in row $i$ ~i~ and column $j$ ~j~ in the matrix represent the kindness of the student sitting in row $i$ ~i~ and column $j$ ~j~. The $n$ ~n~ integers on each line are separated by spaces.