Problem Description

Kiana recently enjoys dining at a very delicious sushi restaurant.

Every evening, the restaurant serves $n$ types of sushi in sequence, with the $i$-th type of sushi having an identifier $a_i$ and a deliciousness value $d_{i, i}$. Different types of sushi may share the same identifier. The restaurant has an unlimited supply of each type of sushi, and Kiana can eat as much sushi as she wants, but she can only take one piece of each type of sushi at a time, and each time she takes sushi, it must be a continuous segment in the order the restaurant serves them. For example, Kiana can take one piece each of the 1st and 2nd types of sushi, or one piece each of the 2nd and 3rd types of sushi, but she cannot take one piece each of the 1st and 3rd types of sushi.

Due to the wide variety of sushi served, and the interaction between different types of sushi: eating salmon sushi and squid sushi together might be great, but eating it with fruit sushi might cause stomachache. Therefore, Kiana defines a combined deliciousness value $d_{i, j} \ (i < j)$, which represents the additional deliciousness gained from eating all the sushi from the $i$-th to the $j$-th type in one go. Since taking sushi takes some time, we consider that the sushi taken in different times do not affect each other. Note that when eating sushi taken at once, multiple combined deliciousness values are added. For example, if Kiana takes one piece each of the 1st, 2nd, and 3rd types of sushi, in addition to $d_{1, 3}$, $d_{1, 2}$ and $d_{2, 3}$ will also be added to the total deliciousness.

Interestingly, Kiana's taste evaluation is memory-based; whether it's the deliciousness of a single type of sushi or the combined deliciousness of multiple types, it will only be added once to Kiana's total deliciousness. For instance, if Kiana takes one piece each of the 1st and 2nd types of sushi at one time, and one piece each of the 2nd and 3rd types of sushi at another time, the total deliciousness from these two times would be $d_{1, 1} + d_{2, 2} + d_{3, 3} + d_{1, 2} + d_{2, 3}$, where $d_{2, 2}$ is only counted once.

Oddly enough, the sushi restaurant has an unusual pricing policy. Specifically, if Kiana has eaten $c \ (c > 0)$ types of sushi with identifier $x$, she needs to pay $mx^2 + cx$ yuan, where $m$ is a constant given by the restaurant.

Now Kiana wants to know the maximum value of the total deliciousness she can get (including the deliciousness of all single types of sushi and all combined deliciousness) minus the total amount of money she has to pay. Since she can't calculate it herself, she hopes you can tell her.

Input Format

The first line contains two positive integers $n, m$, representing the total number of sushi types the restaurant serves and the constant used in calculating the sushi price, respectively.
The second line contains $n$ positive integers, where the $k$-th number $a_k$ represents the identifier of the $k$-th type of sushi.
The next $n$ lines, the $i$-th line contains $n - i + 1$ integers, where the $j$-th number $d_{i, i+j-1}$ represents the corresponding deliciousness value of eating the sushi, as described in the problem statement.

Output Format

Output a single line containing a positive integer, representing the maximum value of the total deliciousness Kiana can get minus the total amount of money she has to pay.

Sample Input and Output

Input Sample #1

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

Output Sample #1

12

Input Sample #2

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

Output Sample #2

381

Input Sample #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

Output Sample #3

1223

Notes/Hints

Sample Explanation 1

In this sample, the restaurant serves $3$ types of sushi with identifiers $a_1 = 2, a_2 = 3, a_3 = 2$, and the constant $m = 1$ for price calculation.

Under the condition that each sushi taken can gain new deliciousness, Kiana has $14$ different ways to eat sushi. Here are a few examples:
1. Kiana eats no sushi, so both the total deliciousness and the total money spent are $0$, and the difference is also $0$;
2. Kiana takes sushi only once, and only the 1st type, i.e., she takes $\{[1, 1]\}$, the total deliciousness is $5$, the total money spent is $1 \times 2^2 + 1 \times 2 = 6$, and the difference is $-1$;
3. Kiana takes sushi twice, first the 1st and 2nd types, then the 2nd and 3rd types, i.e., she takes $\{[1, 2], [2, 3]\}$, the total deliciousness is $5 + (-10) + 15 + (-10) + 15 = 15$, the total money spent is $(1 \times 2^2 + 2 \times 2) + (1 \times 3^2 + 1 \times 3) = 20$, and the difference is $-5$;
4. Kiana takes sushi twice, first the 1st type, then the 3rd type, i.e., she takes $\{[1, 1], [3, 3]\}$, the total deliciousness is $5 + 15 = 20$, the total money spent is $1 \times 2^2 + 2 \times 2 = 8$, and the difference is $12$.

Among the $14$ plans, the only optimal plan is the last one listed, where the maximum value of the total deliciousness minus the total money spent is $12$.

Data Range

For all data, it is guaranteed that $-500 \leq d_{i, j} \leq 500$.

Some special constraints on the data are as follows:

见题面 Input 部分

见题面 Output 部分