AK Tang ate many limited-edition rainbow candies in a game a few days ago, and he felt that his life would be complete if he could just get a limited-edition giant bubble gum. Thus, he embarked on a journey to find the bubble gum.

Guided by mysterious forces, he soon arrived at an ancient city of bubble gum, which is a city with $n \times m$ intersections. Looking down from the sky, these $n \times m$ intersections are neatly arranged into an $n \times m$ grid. Every two adjacent intersections in the horizontal or vertical direction are connected by a street, and each street has a number engraved on it. AK Tang crouched down to pick up a piece of bubble gum, but things were not as simple as they seemed. Indeed, before he could touch the bubble gum, a bubble gum sprite jumped down from the roof and blocked the way between AK Tang and the bubble gum.

I know you are here for the bubble gum, but the bubble gum city was sealed by a bubble gum eater six hundred years ago, and since then, we have not been allowed to enter the city to take the bubble gum. If you can solve the problem left by our guardian sprite hundreds of years ago and lift the seal on the city, then taking a few pieces of bubble gum will not be a big deal.

AK Tang felt that the task was trivial compared to the great bubble gum, and there was no way a problem could stump AK Tang. So he decided to continue.

You must have also discovered that every street in this city has a number engraved on it. When the seal was placed, each intersection also had a number, and the cost of this seal was the sum of the absolute differences of the numbers on all streets.

The cost of a street is calculated as the absolute difference between the numbers at the two intersections it connects.

However, before they could record the numbers at all intersections, some of them disappeared. Only a rough range was recorded in the ancient scrolls.

For the past ten years, everyone has believed that as long as you can calculate the spiritual energy consumed that year, you can lift the seal. After long-term research, people discovered that the ancient city sealed six hundred years ago also participated in many other historical events, and its habit is to achieve its goals with the least amount of spiritual energy.

At this point, AK Tang understood his task. He took a map of the $n \times m$ grid ancient city, which has the numbers engraved on each street, and the range $[a_{i,j}, b_{i,j}]$ for the number at each intersection. When $a = b$, it means the number at this intersection is already determined. Under the premise of satisfying the given conditions, he needs to find the minimum total spiritual energy consumed among all possible scenarios.

Input

The first line contains two integers $n$ and $m$. The meanings are as described in the problem.

Next $m$ lines, each line contains $2n$ integers. The $j$-th number and the $(j+1)$-th number in the $i$-th row are the two parameters $a_{i,j}$ and $b_{i,j}$ for the intersection at row $i$ and column $j$. This indicates that the number at this intersection is in the range $[a_{i,j}, b_{i,j}]$.

Next $m$ lines, each line contains $n-1$ integers. The $j$-th number in the $i$-th row is the number $y_{i,j}$ engraved on the horizontal street connecting intersection $(i, j)$ and intersection $(i, j+1)$.

Next $m-1$ lines, each line contains $n$ integers. The $j$-th number in the $i$-th row is the number $z_{i,j}$ engraved on the vertical street connecting intersection $(i, j)$ and intersection $(i+1, j)$.

It is guaranteed that $a_{i,j} \leq b_{i,j}$, and it is guaranteed to be a grid graph.

Output

Output a single integer representing the minimum total spiritual energy consumed.

Examples

Input 1

3 1
2 2 3 5 5 5
4 4

Output 1

12

Input 2

3 2
0 4 2 6 0 9
4 8 5 10 5 5
7 10
2 9
5 0 9

Output 2

9

Input 3

5 3
42 43 6 8 15 46 32 42 42 48
0 20 2 46 6 6 6 50 9 48
30 39 10 22 12 43 48 48 41 43
23 36 10 10
10 37 12 17
36 42 33 50
0 48 48 2 46
20 10 13 16 11

Output 3

4410

Subtasks

For all data, $1 \leq n \leq 5 \times 10^4$, $1 \leq m \leq 5$, $0 \leq a_{i,j}, b_{i,j}, y_{i,j}, z_{i,j} \leq 10^4$.