#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int MAXN = 2010;const int MAXE = 1000010;const int INF = 0x3fff3fff;struct SAP { int head[MAXN], gap[MAXN], dis[MAXN], pre[MAXN], cur[MAXN]; int to[MAXE], next[MAXE], flow[MAXE], cap[MAXE]; int n, ecnt, st, ed; void init() { memset(head, 0, sizeof(head)); ecnt = 2; } void add_edge(int u, int v, int c) { to[ecnt] = v; cap[ecnt] = c; flow[ecnt] = 0; next[ecnt] = head[u]; head[u] = ecnt++; to[ecnt] = u; cap[ecnt] = 0; flow[ecnt] = 0; next[ecnt] = head[v]; head[v] = ecnt++; } void bfs() { memset(dis, 0x3f, sizeof(dis)); queue<int> que; que.push(ed); dis[ed] = 0; while(!que.empty()) { int u = que.front(); que.pop(); ++gap[dis[u]]; for(int p = head[u]; p; p = next[p]) { int &v = to[p]; if(cap[p ^ 1] > flow[p ^ 1] && dis[v] > n) { dis[v] = dis[u] + 1; que.push(v); } } } } int Max_flow(int ss, int tt, int nn) { st = ss, ed = tt, n = nn; int ans = 0, minFlow = INF, u; for(int i = 0; i <= n; ++i) { cur[i] = head[i]; gap[i] = 0; } u = pre[st] = st; bfs(); while(dis[st] < n) { bool flag = false; for(int &p = cur[u]; p; p = next[p]) { int &v = to[p]; if(cap[p] > flow[p] && dis[u] == dis[v] + 1) { flag = true; minFlow = min(minFlow, cap[p] - flow[p]); pre[v] = u; u = v; if(u == ed) { ans += minFlow; while(u != st) { u = pre[u]; flow[cur[u]] += minFlow; flow[cur[u] ^ 1] -= minFlow; } minFlow = INF; } break; } } if(flag) continue; int minDis = n - 1; for(int p = head[u]; p; p = next[p]) { int &v = to[p]; if(cap[p] > flow[p] && dis[v] < minDis) { minDis = dis[v]; cur[u] = p; } } if(--gap[dis[u]] == 0) break; ++gap[dis[u] = minDis + 1]; u = pre[u]; } return ans; }} G;int n, m, c, d, l, r, x;int f[MAXN], down[MAXE], id[MAXE];int main() { while(scanf("%d%d", &n, &m) != EOF) { G.init(); memset(f, 0, sizeof(f)); int s = n + m + 1, t = s + 1; int ss = t + 1, tt = ss + 1; for(int i = 1; i <= m; ++i) { scanf("%d", &x); f[i] -= x; f[t] += x; G.add_edge(i, t, INF); } int cnt = 0; for(int i = 1; i <= n; ++i) { scanf("%d%d", &c, &d); G.add_edge(s, i + m, d); while(c--) { scanf("%d%d%d", &x, &l, &r); f[i + m] -= l; f[x + 1] += l; down[++cnt] = l; id[cnt] = G.ecnt; G.add_edge(i + m, x + 1, r - l); } } int sum = 0; for(int i = 1; i <= t; ++i) { if(f[i] > 0) sum += f[i], G.add_edge(ss, i, f[i]); else G.add_edge(i, tt, -f[i]); } G.add_edge(t, s, INF); if(sum != G.Max_flow(ss, tt, tt)) puts("-1"); else { printf("%dn", G.Max_flow(s, t, tt)); for(int i = 1; i <= cnt; ++i) printf("%dn", down[i] + G.flow[id[i]]); } puts(""); }}
