Giải bài trực tuyến

Bin Laden the terrorist is hiding in a basement that has M floors below the ground. Each floor has N rooms. The rooms are separated by solid doors that are very hard to break. Each room has doors going to the room below and two rooms beside. From the ground, there are N doors going to N rooms of floor -1. Bin Laden is in the last floor (floor -M), room N (the rightmost room). Each door is made of diffrent kinds of metal, so they require different time to break.

Find the fastest way to go from the ground to Bin Laden's room or he will escape!

Input

• Line 1: M and N
• From line 2 to line 2M+1, even lines contain N numbers, odd lines contain N-1 numbers that are the time required to break the doors.

Output

A single number that is the minimum time to go to Bin Laden's room.

Example

Input
4 2
99 10
1
10 99
1
99 10
1
10 99
1

Output
44

+--99--+--10--+
|      |      |
|      1      |
|      |      |
+--10--+--99--+
|      |      |
|      1      |
|      |      |
+--99--+--10--+
|      |      |
|      1      |
|      |      |
+--10--+--99--+
|      |      |
|      1      |
|      |      |
+------+------+
We may go in zigzag.

Constraints

• 1 <= M <= 2222
• 1 <= N <= 10
• Time to break the doors is in [0, 1000].