Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

BINLADEN - Bin Laden

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].

Added by:VOJ Team
Date:2008-09-05
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET
Resource:VNOI Marathon '08 - Round 12/DivB
Problem Setter: Lê Đôn Khuê

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.