H. The infinite festival
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Yan 'the globe-trotter" Soares continues his trips around the world. In a dream, he recalled that an ancestor of his was Latin American champion of a certain programming competition. Intrigued by this dream, he is heading to Mexico to attend one of these competitions.

Yan is a fan of role-playing games, so he is going to take advantage of this trip to attend the largest role-playing festival in the world. It takes place in the city of Guadalajara, and is composed of $$$N$$$ days where various events take place, and after these $$$N$$$ days, the festival repeats itself again. That's why it's called the "infinite festival".

As it is typical of this kind of festivals, each participant receives a level, in total there are $$$M$$$ levels and every participant starts at level $$$1$$$. Yan has two goals: $$$(a)$$$ to attend the $$$N$$$ days of the festival and, $$$(b)$$$ to reach the level $$$M$$$ during this time. As any good traveler, he would like to do this by spending as little money as possible.

Yan knows the cost $$$c_{ij}$$$ of reaching level $$$i + 1$$$, from level $$$i$$$, on day $$$j$$$. Note that he can go several levels up in one day (even all of them). Also, it knows the cost $$$d_{ij}$$$ of accommodation on day $$$j$$$ if he has level $$$i$$$. Note that the cost of accommodation is paid daily at the end of the day, when the events have finished.

Unfortunately, Yan did not inherit his ancestor's skills. Therefore, he asked you to make a program that calculates the minimum cost of attending the festival. Note that Yan can arrive on any of the $$$N$$$ days to the festival. For instance, if we represent the $$$i$$$-th day of the festival by the integer $$$i$$$ and Yan arrives on day $$$x$$$, then the sequence $$$x, x + 1, \ldots, N, 1, 2, \ldots, x - 1$$$ represents the days he attends to the festival. Note that Yan does not pay for the accommodation of the last day (day $$$x - 1$$$ in the previous example).

Input

The first line contains the integers $$$N$$$ and $$$M$$$ $$$(1 \leq N, M \leq 1500)$$$ as described in the statement. Each of the next $$$M - 1$$$ lines represents the costs $$$c_{ij}$$$ $$$(1 \leq c_{ij} \leq 10^9)$$$. The $$$i$$$-th of these lines contains $$$N$$$ integers representing the cost of reaching level $$$i + 1$$$ from level $$$i$$$ on each of the $$$N$$$ days. Finally, each of the next $$$M$$$ lines represent the costs of accommodation $$$d_{ij}$$$ $$$(1 \leq d_{ij} \leq 10^9)$$$. The $$$i$$$-th of these lines contains $$$N$$$ integers that represent the cost of accommodation if Yan has level $$$i$$$ on each of the $$$N$$$ days.

Output

Print an integer, the minimum cost of attending the $$$N$$$ days of the festival and reaching the level $$$M$$$.

Examples
Input
4 4
43 31 15 20
2 42 3 37
22 39 39 1
17 40 19 58
35 20 35 1
53 1 43 66
16 37 63 67
Output
80
Input
3 5
5 24 1
13 16 15
9 13 3
11 2 16
8 12 3
20 12 13
15 5 19
12 13 6
20 16 2
Output
39
Input
5 3
12 14 13 10 14
12 24 20 8 6
8 9 11 22 25
11 11 25 11 10
5 1 18 21 21
Output
49