#include //#include #pragma GCC optimize("Ofast") using namespace std; #define reps(i,s,n) for(int i = s; i < n; i++) #define rep(i,n) reps(i,0,n) #define Rreps(i,n,e) for(int i = n - 1; i >= e; --i) #define Rrep(i,n) Rreps(i,n,0) #define ALL(a) a.begin(), a.end() using ll = long long; using vec = vector; using mat = vector; ll N,M,H,W,Q,K,A,B; string S; using P = pair; const ll INF = (1LL<<60); template bool chmin(T &a, const T &b){ if(a > b) {a = b; return true;} else return false; } template bool chmax(T &a, const T &b){ if(a < b) {a = b; return true;} else return false; } template void my_printv(std::vector v,bool endline = true){ if(!v.empty()){ for(std::size_t i{}; i; void add_edge(int from, int to, int cap, ll cost, vector &G, bool directed = true){ rep(_, (directed ? 1 : 2)) { G[from].emplace_back(to, cap, cost, (int) G[to].size()); G[to].emplace_back(from, 0, -cost, (int) G[from].size() - 1); swap(to, from); } } bool bellman_ford_for_flow(int s, vector &G, vec &dist){ //O(|V|^2 + |V||E|) dist[s] = 0; int num(0), sz = G.size(); while(num++ < sz){ bool update = false; rep(v, sz){ if(dist[v] != INF) { for (edge &e : G[v]) { if (e.cap > 0 && chmin(dist[e.to], dist[v] + e.cost)) update = true; } } } if(!update) return true; } return false; //failed } mat cost_v, cost_v_first; void dijkstra_for_flow(int s, vector &G, vec &h, vec &dist, vector &prev_v, vector &prev_e){ typedef struct _comp{ ll cost; int v; _comp(){} _comp(ll a, int b){ cost = a; v = b; } bool operator > (const _comp a){ return cost > a.cost; } } mp; priority_queue, greater<> > pque; dist[s] = 0; pque.emplace(0, s); while(!pque.empty()){ mp p = pque.top(); pque.pop(); if(dist[p.v] < p.cost) continue; rep(i, (int)G[p.v].size()){ edge &e = G[p.v][i]; if(p.v < N * 2 && e.to < N * 2){ e.cost = (p.v < e.to ? cost_v.at(p.v).at(e.to - N) : -cost_v.at(e.to).at(p.v - N) + 2); } if(e.cap > 0 && chmin(dist[e.to], p.cost + e.cost + h[p.v] - h[e.to])){ prev_v[e.to] = p.v; prev_e[e.to] = i; pque.emplace(dist[e.to], e.to); } } } } //全然Validateできていないので注意 ll min_cost_flow(int s, int t, int f, vector &G, bool minus_exist = true){ //minus_exist : if (edge.cost < 0) //for graph without negative cycles int sz = G.size(); ll res(0); vector prev_v(sz), prev_e(sz); vec h(sz, minus_exist ? INF : 0); if(minus_exist && (!bellman_ford_for_flow(s, G, h) || h[t] == INF)) return -1; while(f > 0){ vec dist(sz, INF); dijkstra_for_flow(s, G, h, dist, prev_v, prev_e); if(dist[t] == INF) return -1; rep(v, sz) h[v] += dist[v]; int d = f; for(int v = t; v != s; v = prev_v[v]){ chmin(d, G[prev_v[v]][prev_e[v]].cap); } f -= d; res += h[t] * d; for(int v = t; v != s; v = prev_v[v]){ edge &e = G[prev_v[v]][prev_e[v]]; if(v < N * 2 && prev_v[v] < N * 2){ int u = prev_v[v]; if(u < v) { cost_v[u][v - N] += 2; G[v][e.rev].cap = 1; }else { cost_v[v][u - N] -= 2; if (cost_v[v][u - N] == cost_v_first[v][u - N]){ e.cap = 0; } } }else { e.cap -= d; G[v][e.rev].cap += d; } } } return res; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin>>N>>K; const int st = N * 2, gl = N * 2 + 1; vector G(N * 2 + 2); rep(i, N){ cin>>A; add_edge(st, i, A, 0, G); } rep(i, N){ cin>>A; add_edge(i+N, gl, A, 0, G); } ll sum = - (K * 400); cost_v.resize(N); rep(i, N){ cost_v[i].resize(N); reps(j, N, N*2){ cin>>A; sum += A * A; cost_v[i][j-N] = 400 - A * 2 + 1; add_edge(i, j, 1, 0, G); } } cost_v_first = cost_v; cout<