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

Được gửi lên bởi:VOJ Team
Ngày:2008-09-05
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Nguồn bài:VNOI Marathon '08 - Round 12/DivB
Problem Setter: Lê Đôn Khuê

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