题目描述

最近，你从你的曾曾祖父那里继承了一块地。这块地是一个矩形，有 $N$ 行 $M$ 列。你想继续你的高曾祖父的遗产，并开始种植两种植物：小麦和向日葵。

在田地的每个格子里，你可以放两种植物种子中的一种。在细胞 $(i,j)$ 种植小麦可以获得 $A[i][j]$ 欧元，而在同一细胞 $(i,j)$ 种植向日葵可以获得 $B[i][j]$ 欧元。

不幸的是，你很快就会发现，如果你在相邻的细胞中种植不同类型的植物，它们的根会缠在一起，这需要你花一大笔钱来修复。

你现在急切地想知道，如果你在每个细胞中只种植两种植物种子中的一种，你能获得的最大金钱是多少。

输入格式

输入的第一行包含两个整数 $N(1≤N≤70)$ 和 $M(1≤M≤70)$，表示行数和列数。

接下来的 $N$ 行包含 $M$ 个整数 $(1≤A[i][j]≤10^5)$。

接下来的 $N$ 行包含 $M$ 个整数 $(1≤B[i][j]≤10^5)$。

接下来的 $N$ 行将包含 $M−1$ 个整数 $(1≤C_1[i][j]≤10^5)$，表示在细胞 $(i,j)$ 和 $(i,j+1)$ 中播种不同种子的损失。

接下来的 $N-1$ 行将包含 $M$ 个整数 $(1≤C_2[i][j]≤10^5)$，表示在细胞 $(i,j)$ 和 $(i+1,j)$ 中播种不同种子的损失。

输出格式

输出一个数表示答案。

2 2
1 6
7 1
5 1
1 3
1
1
2 1

16