Sushi Tasting Optimization

Kiana loves dining at a famous sushi restaurant. Every evening the restaurant offers n kinds of sushi in order. For each sushi type (i) (with (1\le i\le n)), it has a code (a_i) and an individual tastiness value (d_{i,i}). Note that different sushi types may have the same code. There are infinitely many pieces of each sushi, but in one taking Kiana may only take one piece per sushi type. Moreover, when she takes sushi, she must take a contiguous segment according to the restaurant’s order. That is, she may take sushi types (1,2,3) in one round, or types (2,3) in one round, but she cannot take types (1) and (3) without type (2).

In addition to the individual tastiness (d_{i,i}), if in one round she takes a contiguous segment from sushi type (i) to sushi type (j) (with (i<j)), then an extra combined tastiness (d_{i,j}) is gained for that round. In one round the additional tastiness values of all subintervals are added. For example, if she takes types 1, 2 and 3 in one round then the extra tastiness (d_{1,2}), (d_{2,3}) and (d_{1,3}) are all added. Importantly, each individual sushi’s tastiness and each bonus for a contiguous group is only counted once overall – even if the same sushi is eaten in different rounds, its tastiness is only added a single time, and similarly for any bonus (d_{i,j}). (For example, if in one round she takes sushi types 1 and 2 and in another round types 2 and 3, the total tastiness is (d_{1,1}+d_{2,2}+d_{3,3}+d_{1,2}+d_{2,3}); note that (d_{2,2}) is counted only once.)

However, the charging is rather unusual. For any code (x), if Kiana in total eats (c) pieces of sushi with code (x) ((c>0)), she must pay (m,x^2 + c,x) units of money for those sushi. Here, (m) is a constant provided in the input.

Kiana wants to know the maximum possible value of
(\text{(total tastiness)} - \text{(total cost)}),
considering that she may take sushi rounds arbitrarily (possibly with overlapping sushi picks between rounds). Note that when rounds overlap, an individual sushi eaten more than once only adds its tastiness once, but its cost is incurred each time it is taken. This trade–off can sometimes make it beneficial to deliberately take some sushi more than once in order to gain some bonus tastiness without triggering an unwanted extra bonus (for example, if a larger round would add a negative bonus value).

Input Constraints: For this problem, to allow a brute-force solution, you may assume (1\le n\le 4).

inputFormat

The input begins with two integers (n) and (m) (with (1\le n\le 4)), where (n) is the number of sushi types and (m) is the constant for cost calculation.

Next, a line with (n) integers follows, representing the sushi codes: (a_1,a_2,\dots,a_n).

Then follow (n) lines. The (i)-th line (1-indexed) contains (n-i+1) integers: (d_{i,i}, d_{i,i+1}, \dots, d_{i,n}), representing the individual tastiness and the extra combined tastiness values.

outputFormat

Output a single integer representing the maximum possible value of the total tastiness (including individual sushi and bonus combined tastiness values, counted only once each) minus the total cost.

sample

3 1
1 2 1
5 2 -1
3 4
6

11