Happiness

Problem Source

BZOJ 2127

Problem Description

The seating chart of class 1, grade 10 is an $n \times m$ matrix. After a semester together, every student has become good friends with the classmates directly in front of, behind, to the left of, and to the right of them.

This semester the class must split into the arts and the sciences. Each student has their own joy value for choosing arts versus sciences, and a pair of good friends who choose the same subject (both arts or both sciences) earns some extra joy. As the computer-competition coach (and big boss) scp, you want to know how to assign the subjects so that the total joy of the whole class is maximized.

Input Format

The first line contains two positive integers $n, m\ (1 \le n, m \le 100)$. Then follow six matrices in total.

The first two matrices are $n$ rows by $m$ columns, giving the joy values for choosing arts and for choosing sciences, respectively.

The next two matrices are $(n-1)$ rows by $m$ columns, giving the extra joy when front-and-back neighbors both choose arts and both choose sciences, respectively.

The last two matrices are $n$ rows by $(m-1)$ columns, giving the extra joy when left-and-right neighbors both choose arts and both choose sciences, respectively.

All joy values are non-negative integers not exceeding $5000$.

Output Format

Output one integer: the maximum possible total joy.

Sample Input

1 2
1 1
100 110
1
1000

Sample Output

1210