【bzoj2055】80人环游世界

2014年6月17日2,5170

Description

Input

第一行两个正整数N,M。第二行有N个不大于M正整数,分别表示V1,V2……VN。接下来有N ¡ 1行。第i行有N ¡ i个整数,该行的第j个数表示从第i个国家到第i + j个国家的机票费(如果该值等于¡1则表示这两个国家间没有通航)。

Output

在第一行输出最少的总费用。

Sample Input

6 3
2 1 3 1 2 1
2 6 8 5 0
8 2 4 1
6 1 0
4 -1
4

Sample Output

27

HINT

1<= N < =100 1<= M <= 79

题解

m个人的起始点任意。。。

这什么奇怪的设定。。

知道这个以后随便写个上下界费用流就差不多了