1309: #2146. 「SHOI2017」寿司餐厅

第一行包含两个正整数 $n,m$，分别表示这家餐厅提供的寿司总数和计算寿司价格中使用的常数。
第二行包含 $n$ 个正整数，其中第 $k$ 个数 aka_ka​k​​ 表示第 $k$ 份寿司的代号。
接下来 $n$ 行，第 $i$ 行包含 $n-i+1$ 个整数，其中第 $j$ 个数 di,i+j−1d_{i, i+j-1}d​i,i+j−1​​ 表示吃掉寿司能获得的相应的美味度，具体含义见问题描述。

输出共一行包含一个正整数，表示 Kiana 能获得的总美味度减去花费的总钱数的最大值。

样例输入 1

3 1
2 3 2
5 -10 15
-10 15
15

样例输出 1

12

样例解释 1

在这组样例中，餐厅一共提供了 $3$ 份寿司，它们的代号依次为 a1=2,a2=3,a3=2a_1 = 2, a_2 = 3, a_3 = 2a​1​​=2,a​2​​=3,a​3​​=2，计算价格时的常数 $m=1$。

在保证每次取寿司都能获得新的美味度的前提下，Kiana 一共有 $14$ 种不同的吃寿司方案。以下列出其中几种：

1. Kiana 一个寿司也不吃，这样她获得的总美味度和花费的总钱数都是 $0$，两者相减也是 $0$；
2. Kiana 只取 $1$ 次寿司，且只取第 $1$ 个寿司，即她取寿司的情况为 $\{[1,1]\}$，这样获得的总美味度为 $5$，花费的总钱数为 1×22+1×2=61 \times 2^2 + 1 \times 2 = 61×2​2​​+1×2=6，两者相减为 $-1$；
3. Kiana 取 $2$ 次寿司，第一次取第 $1,2$ 个寿司，第二次取第 $2,3$ 个寿司，即她取寿司的情况为 $\{[1,2],[2,3]\}$，这样获得的总美味度为 $5+(-10)+15+(-10)+15=15$，花费的总钱数为 (1×22+2×2)+(1×32+1×3)=20(1 \times 2^2 + 2 \times 2) + (1 \times 3^2 + 1 \times 3) = 20(1×2​2​​+2×2)+(1×3​2​​+1×3)=20，两者相减为 $-5$；
4. Kiana 取 $2$ 次寿司，第一次取第 $1$ 个寿司，第二次取第 $3$ 个寿司，即她取寿司的情况为 $\{[1,1],[3,3]\}$，这样获得的总美味度为 $5+15=20$，花费的总钱数为 1×22+2×2=81 \times 2^2 + 2 \times 2 = 81×2​2​​+2×2=8，两者相减为 $12$。

在 $14$ 种方案中，惟一的最优方案是列出的最后一种方案，这时她获得的总美味度减去花费的总钱数的值最大为 $12$。

样例输入 2

5 0
1 4 1 3 4
50 99 8 -39 30
68 27 -75 -32
70 24 72
-10 81
-95

样例输出 2

381

样例输入 3

10 1
5 5 4 4 1 2 5 1 5 3
83 91 72 29 22 -5 57 -14 -36 -3
-11 34 45 96 32 73 -1 0 29
-48 68 44 -5 96 66 17 74
88 47 69 -9 2 25 -49
86 -9 -77 62 -10 -30
2 40 95 -74 46
49 -52 2 -51
-55 50 -44
72 22
-68

样例输出 3

1223

对于所有数据，保证 −500≤di,j≤500-500 \leq d_{i, j} \leq 500−500≤d​i,j​​≤500。

数据的一些特殊约定如下表：