Kiana recently started enjoying dining at a delicious sushi restaurant.

Every evening, the restaurant serves $n$ types of sushi in a specific order. The $i$-th sushi has a code $a_i$ and a deliciousness value $d_{i,i}$. Different types of sushi may share the same code. Each type of sushi is available in infinite supply, and Kiana can take sushi to eat an unlimited number of times. However, she can only take one piece of each sushi at a time, and each time she takes sushi, it must be a contiguous segment of the sushi provided by the restaurant. That is, Kiana can take one piece of each of the $1^{st}$ and $2^{nd}$ sushi at once, or one piece of each of the $2^{nd}$ and $3^{rd}$ sushi at once, but she cannot take the $1^{st}$ and $3^{rd}$ sushi at once without taking the $2^{nd}$.

Because the restaurant offers a wide variety of sushi, different types of sushi influence each other: salmon sushi and squid sushi might taste great together, but eating them with fruit sushi might cause a stomachache. Therefore, Kiana defines a comprehensive deliciousness $d_{i,j} (i < j)$, which represents the additional deliciousness gained after eating all the sushi from the $i$-th to the $j$-th piece if they are included in a single serving. Since taking sushi takes time, we assume that sushi taken in two different servings do not influence each other. Note that when eating a single serving of sushi, more than one comprehensive deliciousness value may be added. For example, if Kiana takes one piece each of the $1^{st}, 2^{nd},$ and $3^{rd}$ sushi, then in addition to $d_{1,3}$, the values $d_{1,2}$ and $d_{2,3}$ are also added to the total deliciousness.

Interestingly, Kiana's gourmet evaluation criteria have a memory effect. Whether it is the deliciousness of a single type of sushi or the comprehensive deliciousness of a combination of multiple sushi, it is only added to Kiana's total deliciousness once. For example, if Kiana takes one piece each of the $1^{st}$ and $2^{nd}$ sushi in one serving, and one piece each of the $2^{nd}$ and $3^{rd}$ sushi in another, the total deliciousness of these two servings is $d_{1,1} + d_{2,2} + d_{3,3} + d_{1,2} + d_{2,3}$, where $d_{2,2}$ is only counted once.

Strangely, the restaurant's pricing policy is quite unusual. Specifically, if Kiana has eaten a total of $c$ pieces of sushi with code $x$, she must pay $mx^2 + cx$ for these pieces, where $m$ is a constant provided by the restaurant.

Now, Kiana wants to know the maximum value of the total deliciousness she can obtain (including the deliciousness of all individual pieces eaten and all accumulated comprehensive deliciousness) minus the total cost. Since she cannot calculate this herself, she hopes you can tell her.

Input

The first line contains two positive integers $n$ and $m$, representing the total number of sushi provided by the restaurant 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 code of the $k$-th sushi.

The next $n$ lines contain $n - i + 1$ integers each, where the $j$-th number in the $i$-th line represents $d_{i, i+j-1}$, the corresponding deliciousness gained from eating that sushi, with the specific meaning as described in the problem statement.

Output

Output a single line containing a positive integer, representing the maximum value of the total deliciousness minus the total cost.

Examples

Input 1

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

Output 1

12

Input 2

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

Output 2

381

Input 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 3

1223

Subtasks

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

The special constraints for the data are as follows: