题意：
给出\(n\)份寿司，现可以选取任意多次连续区间内的寿司，对于区间\([l,r]\)，那么贡献为\(\sum_{i=l}^r \sum_{j=i}^rd_{i,j}\)（对于相同的\(d_{i,j}\)只会计算一次）。
每种寿司都有一个标签\(a_i\)，若选了\(c\)种标签为\(a_i\)的寿司，此时花费\(ma_i^2+ca_i\)。
问最终最大价值为多少。
思路：
- 因为对于任意一个区间\([l,r]\)，其选择过后，内部区间贡献都要算上，并且每种贡献只算一次。这种严格先后关系并且要求不计算重复的问题，考虑最大权闭合子图。
- 我们将每个\(d_{i,j}\)抽象成点来建立有向图，易知\(d_{i,j}\)向\(d_{i+1,j},d_{i,j-1}\)连边，权值即为\(d_{i,j}\)。
- 考虑如何处理\(ma_i^2+ca_i\)：对于标签为\(a_i\)的寿司，我们每选一种，会多出\(c_i\)；如果选了标签为\(a_i\)，那么就会多出\(ma_i^2\)。所以对于每个\(d_{i,i}\)，直接向\(a_i\)连边，表示选了之后会有\(ma_i^2\)的贡献；同时，将\(d_{i,i}\)的权值减去\(a_i\)，这样即可处理\(ca_i\)。
- 有向图以及每个点的点权知道后，接下来就直接类似于最大权闭合子图那样建边即可。
代码如下：
/*
* Author: heyuhhh
* Created Time: 2019/10/30 12:45:44
*/
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '\n'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e4 + 5;
#define _S heyuhhh
template <class T>
struct Dinic{
struct Edge{
int v, next;
T flow;
Edge(){}
Edge(int v, int next, T flow) : v(v), next(next), flow(flow) {}
}e[N * 10];
int head[N], tot;
int dep[N];
void init() {
memset(head, -1, sizeof(head)); tot = 0;
}
void adde(int u, int v, T w, T rw = 0) {
e[tot] = Edge(v, head[u], w);
head[u] = tot++;
e[tot] = Edge(u, head[v], rw);
head[v] = tot++;
}
bool BFS(int _S, int _T) {
memset(dep, 0, sizeof(dep));
queue <int> q; q.push(_S); dep[_S] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = head[u]; ~i; i = e[i].next) {
int v = e[i].v;
if(!dep[v] && e[i].flow > 0) {
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[_T] != 0;
}
T dfs(int _S, int _T, T a) {
T flow = 0, f;
if(_S == _T || a == 0) return a;
for(int i = head[_S]; ~i; i = e[i].next) {
int v = e[i].v;
if(dep[v] != dep[_S] + 1) continue;
f = dfs(v, _T, min(a, e[i].flow));
if(f) {
e[i].flow -= f;
e[i ^ 1].flow += f;
flow += f;
a -= f;
if(a == 0) break;
}
}
if(!flow) dep[_S] = -1;
return flow;
}
T dinic(int _S, int _T) {
T max_flow = 0;
while(BFS(_S, _T)) max_flow += dfs(_S, _T, INF);
return max_flow;
}
};
Dinic <int> solver;
int n, m;
int a[105], Id[105][105], F[105][105];
void run(){
solver.init();
int Max = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
Max = max(a[i], Max);
}
int cnt = 2;
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
cin >> F[i][j];
Id[i][j] = ++cnt;
}
}
int S = 1, T = 2;
int ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
int cost = F[i][j];
if(i == j) {
if(m) solver.adde(Id[i][j], cnt + a[i], INF);
cost -= a[i];
} else {
solver.adde(Id[i][j], Id[i][j - 1], INF);
solver.adde(Id[i][j], Id[i + 1][j], INF);
}
if(cost > 0) solver.adde(S, Id[i][j], cost), ans += cost;
else solver.adde(Id[i][j], T, -cost);
}
}
for(int i = 1; i <= Max; i++) {
solver.adde(++cnt, T, m * i * i);
}
dbg(1);
ans -= solver.dinic(S, T);
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin >> n >> m) run();
return 0;
}