80人环游世界

想必大家都看过成龙主演的《 $80$ 天环游世界》，其中紧张刺激的打斗场面一定给你留下了深刻的印象。现在有一个由 $80$ 人组成的团体，也想进行一次环球旅行。

他们打算兵分多路，游遍每一个国家。由于他们主要分布在东方，因此旅行时只会向西方前进。按照从东到西的顺序，将所有国家依次编号为 $1,2,\ldots,N$ 。若第 $i$ 个人的游历路线为 $P_1,P_2,\ldots,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,\ldots,V_N$ ，其中 $V_i$ 表示有且仅有 $V_i$ 个人会经过第 $i$ 个国家。

接下来输入 $N-1$ 行机票费用。第 $i$ 行包含 $N-i$ 个整数，其中第 $j$ 个整数 $C_{i,i+j}$ 表示从第 $i$ 个国家飞往第 $i+j$ 个国家的机票费用。

对于每个 $C_{i,j}$ ，其值为 $-1$ 或非负整数。若 $C_{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

本题题面与测试数据整理自 BZOJ。

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