P6545 [CEOI 2014] The Wall
题目背景
CEOI2014 Day2 T3，译者：小粉兔
题目描述
Rectos 岛经常遭受洪水的泛滥和海盗的侵扰，所以 Rectos 的国王想要建造一堵城墙以保护岛上所有的村庄。
Rectos 是一个矩形岛屿，所以城墙的设计师将岛屿看作一个正方形网格。每个村庄都位于其中的某个方格中，并且首都村庄位于整座岛的西北角，也就是最左上角的方格中。
必须保证从外部（也就是整个网格的外部）在不越过城墙的条件下，是到达不了任何一个村庄的。
设计师计划城墙将只沿着网格线建造，更具体地说是按照如下方法：他将第一段城墙置于最左上角延伸出的两条网格线之一上，并且下一段城墙总是和上一段城墙首尾相连，不断重复这一过程直到又一次回到最左上角为止。这一过程可能会导致一段网格线上放置了大于一段的城墙，总而言之，城墙是沿着网格线上的一条连续闭曲线建造的。
地势测量表明，在每一段网格线上建造一段城墙都需要一定的花费。建造城墙的总花费就是建造每一段城墙的花费之和。如果在某一段网格线上建造了 $t$ 段城墙，则花费也要重复计算 $t$ 次。
国王想要花费尽量少的钱建好城墙。请你帮助国王，编写一个程序，给出村庄的位置以及每一段网格线上的建造花费，计算建造城墙所需最小的花费。
输入格式
无
输出格式
无
说明/提示
**【样例 #1 解释】**
**【样例 #2 解释】**
**【数据范围与提示】**
对于所有数据，保证 $1 \le n, m \le 400$，对于所有的建造花费 $v$，有 $1 \le v \le {10}^9$。
| 子任务编号 | 分值 | 特殊限制 |
| :-: | :-: | :-: |
| $1$ | $30$ | $n, m \le 40$ 且村庄的数量不超过 $10$ |
| $2$ | $30$ | $n, m \le 40$ |
| $3$ | $40$ | 无特殊限制 |