P4553 80 人环游世界

想必大家都看过成龙大哥的《80 天环游世界》，里面的紧张刺激的打斗场面一定给你留下了深刻的印象。现在就有这么一个 80 人的团伙，也想来一次环游世界。 他们打算兵分多路，游遍每一个国家。 因为他们主要分布在东方，所以他们只朝西方进军。设从东方到西方的每一个国家的编号依次为 $1, \cdots, N$。假若第 $i$ 个人的游历路线为 $P_1,P_2,\cdots ,P_k\ (0\le k\le N)$，则 $P_1

第一行两个正整数 $N, M$。 第二行有 $N$ 个不大于 $M$ 的正整数，分别表示 $V_1,V_2,\cdots, V_N$。 接下来有 $N - 1$ 行。第 $i$ 行有 $N - i$ 个整数，该行的第 $j$ 个数表示从第 $i$ 个国家到第 $i + j$ 个国家的机票费（如果该值等于 $-1$ 则表示这两个国家间没有通航）。

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

在 $10\%$ 的数据中，$M=1$； 在 $20\%$ 的数据中，$1\le M\le 2$； 在 $40\%$ 的数据中，$1\le M\le 3$； 在 $60\%$ 的数据中，$1\le M\le 4$； 在 $100\%$ 的数据中，$1 \le N\le 100$，$1\le M\le 79$。 保证所以输入数据中最少费用小于 $10^6$。 保证至少存在一种可行方案。 纪中联赛模拟题 BY CQF