A. 除草

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

小牛拥有着一个 1\times n 的草场。这个草场比较的神奇,每一个草都有一个美味值。小牛比较的贪心,他会优先吃掉美味值较小的草。题目会给出一个 n\times n 的表格,代表着两两草之间的大小比较关系,如下图所示。( a 为该位置草的美味值并且保证这个图不会有冲突)

a_1 a_2 a_3 a_4
a_1 = > = <
a_2 < = < <
a_3 = > = <
a_4 > > > =

那么这个图所表示的是

mlwGlR.png

但困难的是,小牛自己不会割草,他要请割草工来帮忙他割草。一共有 m-1 个割草工,编号为 2~m ,每两两之间有道路相连接。

我们的小牛开始从 1 位置出发,割完草之后回到 1 位置。每次请求当前割草工帮忙割草(也就是说割草严格要求从美味度小的向美味度大的割)。

割草工一次性能割完一种美味度的草,并且请这个割草工所要的花费为当前美味度的草的个数 \times 当前位置走向这个割草工路径的长度。

聪明的你能帮助小牛,如何花费最小的费用,割完这个草场?

输入格式

一个正整数 n ,代表当前草场的长度。

一个 n\times n 的图,代表着当前草场每个位置的两两美味值的比较。

一个正整数 m ,代表割草工的个数加上小牛的起始点。( m-1 严格等于美味值的总数)

以下 m 行,每行 m 个正整数。两两位置之间的距离。

输出格式

一个正整数,代表割完这个草场所花最小花费。

样例

输入

4 
= > = < 
< = < < 
= > = <
> > > = 
4 
0 1 2 1 
0 0 1 1 
0 2 0 3 
0 1 3 0 

输出

4 
走的路径为1->4->2->3->1(1*1+1*2+1*1)

数据范围与提示

从开始的位置到每一个割草工的位置的距离值都是给定的 \

从每一个割草工到开始的位置是不需要花钱的 \

30% 0<m<n<=10

60% m\leq 15,n\leq100

100% m\leq 18,n\leq1000