Luogu P1006 - Passing notes

Alice and Bob are good friends and classmates, they always talk about endless topics together. In a quality development activity, the classmates were arranged to make a matrix with $m$ rows and $n$ columns, and Alice and Bob 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. Alice sits in the upper left corner of the matrix with coordinates $(1,1)$ , and Bob sits in the lower right corner of the matrix with coordinates $(m,n)$ . The note passed from Alice to Bob can only be passed down or to the right , and the note passed from Bob to Alice can only be passed up or to the left .

During the activity, Alice hoped to pass a note to Bob, and also hoped that Bob would reply to her. Every classmate in the class can help them, but only once. That is to say, if the person helped when Alice handed the note to Bob, he would not help when Bob handed it to Alice, and vice versa.

There is one more thing that needs to be paid attention to. Each student in the class is willing to help with a high or low degree of goodwill (note: the degree of kindness of Alice and Bob is not defined, use 0 when entering), which is an integer between $[0,100]$ , and the larger the number, the more kind the student is. Alice and Bob hope to find as many kind students as possible to help pass the note, that is, to find two back and forth transmission paths, so that the sum of the degree of goodwill of the students on these two paths is maximized .

Now, please help Alice and Bob find such two paths.

How to submit:

The pastebin below has $10$ inputs. Each input has the format:

• Two numbers $m,n$ , the number of rows and columns of the matrix.

• The next $m$ rows are an $m \times n$ matrix. The integer in the $i \th$ row and $j \th$ column of the matrix represents the degree of goodwill of the students sitting in the $i \th$ row and $j \th$ column. The $n$ integers on each line are separated by spaces.

The output is an integer, which represents the * maximum * value of the sum of the degree of goodwill of the students who participated in passing the note on two roads back and forth.

Then submit the sum of all of the outputs.

Input restrictions:

Input $1 \sim 3$ : $1 \leq n,m \leq 10$ .

Input $4 \sim 10$ : $1 \leq n,m \leq 50$ .

Inputs are here

Note: This problem is very similar to Luogu P1004 - Square access , except that the two paths can't cross each other.

---

Luogu Problem Set