题目描述

想必大家都看过成龙大哥的《80 天环游世界》，里面的紧张刺激的打斗场面一定给你留下了深刻的印象。现在就有这么一个 80 人的团伙，也想来一次环游世界。

他们打算兵分多路，游遍每一个国家。

因为他们主要分布在东方，所以他们只朝西方进军。设从东方到西方的每一个国家的编号依次为 $1, \cdots, N$。假若第 $i$ 个人的游历路线为 $P_1,P_2,\cdots ,P_k\ (0\le k\le N)$，则 $P_1<P_2<\cdots <P_k$。

众所周知，中国相当美丽，这样在环游世界时就有很多人经过中国。我们用一个正整数 $V_i$ 来描述一个国家的吸引程度，$V_i$ 值越大表示该国家越有吸引力，同时也表示有且仅有 $V_i$ 个人会经过那一个国家。

为了节省时间，他们打算通过坐飞机来完成环游世界的任务。同时为了省钱，他们希望总的机票费最小。

明天就要出发了，可是有些人临阵脱逃，最终只剩下了 $M$ 个人去环游世界。他们想知道最少的总费用，你能告诉他们吗？

输入格式

第一行两个正整数 $N, M$。

第二行有 $N$ 个不大于 $M$ 的正整数，分别表示 $V_1,V_2,\cdots, V_N$。

接下来有 $N - 1$ 行。第 $i$ 行有 $N - i$ 个整数，该行的第 $j$ 个数表示从第 $i$ 个国家到第 $i + j$ 个国家的机票费（如果该值等于 $-1$ 则表示这两个国家间没有通航）。

输出格式

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

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

27

提示

在 $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