Problem1077--#2146. 「SHOI2017」寿司餐厅

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

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

Kiana 最近喜欢到一家非常美味的寿司餐厅用餐。

每天晚上,这家餐厅都会按顺序提供 nnn 种寿司,第 iii 种寿司有一个代号 aia_iai 和美味度 di,id_{i, i}di,i,不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的,Kiana 也可以无限次取寿司来吃,但每种寿司每次只能取一份,且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段,即 Kiana 可以一次取走第 1,21, 21,2 种寿司各一份,也可以一次取走第 2,32, 32,3 种寿司各一份,但不可以一次取走第 1,31, 31,3 种寿司。

由于餐厅提供的寿司种类繁多,而不同种类的寿司之间相互会有影响:三文鱼寿司和鱿鱼寿司一起吃或许会很棒,但和水果寿司一起吃就可能会肚子痛。因此,Kiana 定义了一个综合美味度 di,j (i<j)d_{i, j} \ (i < j)di,j (i<j),表示在一次取的寿司中,如果包含了餐厅提供的从第 iii 份到第 jjj 份的所有寿司,吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司需要花费一些时间,所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次取的寿司时,不止一个综合美味度会被累加,比如若 Kiana 一次取走了第 1,2,31, 2, 31,2,3 种寿司各一份,除了 d1,3d_{1, 3}d1,3 以外,d1,2,d2,3d_{1, 2}, d_{2, 3}d1,2,d2,3 也会被累加进总美味度中。

神奇的是,Kiana 的美食评判标准是有记忆性的,无论是单种寿司的美味度,还是多种寿司组合起来的综合美味度,在计入 Kiana 的总美味度时都只会被累加一次。比如,若 Kiana 某一次取走了第 1,21, 21,2 种寿司各一份,另一次取走了第 2,32, 32,3 种寿司各一份,那么这两次取寿司的总美味度为 d1,1+d2,2+d3,3+d1,2+d2,3d_{1, 1} + d_{2, 2} + d_{3, 3} + d_{1, 2} + d_{2, 3}d1,1+d2,2+d3,3+d1,2+d2,3,其中 d2,2d_{2, 2}d2,2 只会计算一次。

奇怪的是,这家寿司餐厅的收费标准很不同寻常。具体来说,如果 Kiana 一共吃过了 c (c>0)c \ (c > 0)c (c>0) 代号为 xxx 的寿司,则她需要为这些寿司付出 mx2+cxmx^2 + cxmx2+cx 元钱,其中 mmm 是餐厅给出的一个常数。

现在 Kiana 想知道,在这家餐厅吃寿司,自己能获得的总美味度(包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度)减去花费的总钱数的最大值是多少。由于她不会算,所以希望由你告诉她。

输入格式

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

输出格式

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

样例

样例输入 1

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

样例输出 1

12

样例解释 1

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

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

  1. Kiana 一个寿司也不吃,这样她获得的总美味度和花费的总钱数都是 000,两者相减也是 000
  2. Kiana 只取 111 次寿司,且只取第 111 个寿司,即她取寿司的情况为 {[1,1]}\{[1, 1]\}{[1,1]},这样获得的总美味度为 555,花费的总钱数为 1×22+1×2=61 \times 2^2 + 1 \times 2 = 61×22+1×2=6,两者相减为 −1-11
  3. Kiana 取 222 次寿司,第一次取第 1,21, 21,2 个寿司,第二次取第 2,32, 32,3 个寿司,即她取寿司的情况为 {[1,2],[2,3]}\{[1, 2], [2, 3]\}{[1,2],[2,3]},这样获得的总美味度为 5+(−10)+15+(−10)+15=155 + (-10) + 15 + (-10) + 15 = 155+(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×22+2×2)+(1×32+1×3)=20,两者相减为 −5-55
  4. Kiana 取 222 次寿司,第一次取第 111 个寿司,第二次取第 333 个寿司,即她取寿司的情况为 {[1,1],[3,3]}\{[1, 1], [3, 3]\}{[1,1],[3,3]},这样获得的总美味度为 5+15=205 + 15 = 205+15=20,花费的总钱数为 1×22+2×2=81 \times 2^2 + 2 \times 2 = 81×22+2×2=8,两者相减为 121212

141414 种方案中,惟一的最优方案是列出的最后一种方案,这时她获得的总美味度减去花费的总钱数的值最大为 121212

样例输入 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 500500di,j500

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

Case # nnn aia_iai mmm 附加限制
1 ≤2\leq 22 ≤30\leq 3030 =0= 0=0 -
2 =1= 1=1
3 ≤3\leq 33 =0= 0=0
4 =1= 1=1
5 ≤5\leq 55 =0= 0=0
6 =1= 1=1
7 ≤10\leq 1010 =0= 0=0 所有的 aia_iai 相同
8 =1= 1=1 -
9 ≤15\leq 1515 =0= 0=0 所有的 aia_iai 相同
10 =1= 1=1 -
11 ≤30\leq 3030 ≤1000\leq 10001000 =0= 0=0 所有的 aia_iai 相同
12 ≤30\leq 3030 =0= 0=0
13 ≤1000\leq 10001000 =0= 0=0 -
14 =1= 1=1
15 ≤50\leq 50

Source/Category