(mathcal{Description})
Link.
美食节提供 (n) 种菜品，第 (i) 种的需求量是 (p_i)，菜品由 (m) 个厨师负责制作，第 (j) 个厨师做第 (i) 道菜的用时是 (t_{ij})。安排做菜方案，使得 (sum p_i) 个需求等待的总时间最小。
(nle40)，(mle100)，(sum p_ile800)。
(mathcal{Solution})
对于每个厨师，他做他所负责的倒数第 (i) 道菜的额外贡献系数为 (i)，即其对答案贡献 (i imes) 做该道菜的用时。所以想到已时间为层建分层图，菜品令为 (d_1,d_2,cdots,d_n)，第 (i) 个厨师拆为 (i_1,i_2,cdots,i_n)，表示做倒数第 (1) 道菜的 (i) 厨师，做倒数第二道菜的 (i) 厨师，……，做倒数第 (n) 道菜的 (i) 厨师。每个 (d_k) 向 (i_j) 连一条费用为 (jt_{ki}) 的边，其余边自行脑补，跑最小费用最大流即可。
然而 (mathcal O(operatorname{Dinic}(nm,n^2m))) 并跑不过，需要用动态加点的优化方法：当某个厨师用到了 (i_j) 这一虚点时，再加入 (i_{j+1}) 及其连边。
(mathcal{Code})
/* Clearink */
#include <queue>
#include <cstdio>
#include <cassert>
#include <algorithm>
#define rep( i, l, r ) for ( int i = l, repEnd##i = r; i <= repEnd##i; ++i )
#define per( i, r, l ) for ( int i = r, repEnd##i = l; i >= repEnd##i; --i )
typedef std::pair<int, int> PII;
inline int rint () {
int x = 0; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () );
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x;
}
inline int imin ( const int a, const int b ) { return a < b ? a : b; }
const int MAXN = 40, MAXM = 100, MAXND = 1e4, INF = 0x3f3f3f3f;
int n, m, cook[MAXN + 5][MAXM + 5], bel[MAXND + 5], stp[MAXM + 5], vis[MAXND + 5];
struct MaxFlowCostGraph {
static const int MAXND = ::MAXND, MAXEG = 2e6;
int ecnt, head[MAXND + 5], S, T, bound, curh[MAXND + 5], d[MAXND + 5];
bool inq[MAXND + 5];
struct Edge { int to, flw, cst, nxt; } graph[MAXEG * 2 + 5];
MaxFlowCostGraph (): ecnt ( 1 ) {}
inline void link ( const int s, const int t, const int f, const int w ) {
graph[++ecnt] = { t, f, w, head[s] };
head[s] = ecnt;
}
inline Edge& operator [] ( const int k ) { return graph[k]; }
inline void operator () ( const int s, const int t, const int f, const int w ) {
#ifdef RYBY
printf ( "%d %d ", s, t );
if ( f == INF ) printf ( "INF " );
else printf ( "%d ", f );
printf ( "%d
", w );
#endif
link ( s, t, f, w ), link ( t, s, 0, -w );
}
inline bool spfa () {
static std::queue<int> que;
for ( int i = 0; i <= bound; ++i ) d[i] = -1, inq[i] = false;
d[S] = 0, inq[S] = true, que.push ( S );
while ( !que.empty () ) {
int u = que.front (); que.pop ();
inq[u] = false;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( graph[i].flw
&& ( !~d[v = graph[i].to] || d[v] > d[u] + graph[i].cst ) ) {
d[v] = d[u] + graph[i].cst;
if ( !inq[v] ) que.push ( v ), inq[v] = true;
}
}
}
return ~d[T];
}
inline PII dfs ( const int u, const int iflw ) {
if ( u == T ) return { iflw, 0 };
inq[u] = true; PII ret ( 0, 0 );
for ( int& i = curh[u], v; i; i = graph[i].nxt ) {
if ( graph[i].flw && !inq[v = graph[i].to]
&& d[v] == d[u] + graph[i].cst ) {
PII oflw ( dfs ( v, imin ( iflw - ret.first, graph[i].flw ) ) );
graph[i].flw -= oflw.first, graph[i ^ 1].flw += oflw.first;
ret.first += oflw.first;
ret.second += graph[i].cst * oflw.first + oflw.second;
if ( ret.first == iflw ) break;
}
}
if ( !ret.first ) d[u] = -1;
return inq[u] = false, ret;
}
} graph;
int main () {
n = rint (), m = rint ();
int S = 0, T = graph.bound = 1e4, cnt = n;
rep ( i, 1, n ) graph ( S, i, rint (), 0 );
rep ( i, 1, n ) rep ( j, 1, m ) cook[i][j] = rint ();
rep ( i, 1, m ) {
graph ( ++cnt, T, 1, 0 ), bel[cnt] = i, stp[i] = 1;
rep ( j, 1, n ) graph ( j, cnt, 1, cook[j][i] );
}
graph.S = S, graph.T = T;
int ans = 0;
while ( graph.spfa () ) {
for ( int i = 0; i <= graph.bound; ++i ) {
graph.inq[i] = false, graph.curh[i] = graph.head[i];
}
ans += graph.dfs ( S, INF ).second;
for ( int i = graph.head[T], v, cid; i; i = graph[i].nxt ) {
if ( graph[i].flw && !vis[v = graph[i].to] ) {
vis[v] = true, cid = bel[v];
graph ( ++cnt, T, 1, 0 ), ++stp[bel[cnt] = cid];
rep ( j, 1, n ) graph ( j, cnt, 1, stp[cid] * cook[j][cid] );
}
}
}
printf ( "%d
", ans );
return 0;
}