1 /**  2  * bzoj  3  * Problem#1391  4  * Accepted  5  * Time:4860ms  6  * Memory:46372k  7  */  8 #include <iostream>  9 #include <cstdio> 10 #include <ctime> 11 #include <cmath> 12 #include <cctype> 13 #include <cstring> 14 #include <cstdlib> 15 #include <fstream> 16 #include <sstream> 17 #include <algorithm> 18 #include <map> 19 #include <set> 20 #include <stack> 21 #include <queue> 22 #include <vector> 23 #include <stack> 24 #ifndef WIN32 25 #define Auto "%lld" 26 #else 27 #define Auto "%I64d" 28 #endif 29 using namespace std; 30 typedef bool boolean; 31 const signed int inf = (signed)((1u << 31) - 1); 32 const int eps = 1e-6; 33 #define smin(a, b) a = min(a, b) 34 #define smax(a, b) a = max(a, b) 35 #define max3(a, b, c) max(a, max(b, c)) 36 #define min3(a, b, c) min(a, min(b, c)) 37 template<typename T> 38 inline boolean readInteger(T& u){ 39     char x; 40     int aFlag = 1; 41     while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 42     if(x == -1) { 43         ungetc(x, stdin);     44         return false; 45     } 46     if(x == ‘-‘){ 47         x = getchar(); 48         aFlag = -1; 49     } 50     for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 51     ungetc(x, stdin); 52     u *= aFlag; 53     return true; 54 } 55  56 typedef class Edge { 57     public: 58         int end; 59         int next; 60         int flow; 61         int cap; 62         Edge(int end = 0, int next = -1, int flow = 0, int cap = 0):end(end), next(next), flow(flow), cap(cap) {    } 63 }Edge; 64  65 typedef class MapManager { 66     public: 67         int ce; 68         Edge* edge; 69         int* h; 70          71         MapManager():ce(0), h(NULL) {        } 72         MapManager(int nodes, int limit):ce(0) { 73             h = new int[(const int)(nodes + 1)]; 74             edge = new Edge[(const int)(limit + 1)]; 75             memset(h, -1, sizeof(int) * (nodes + 1)); 76         } 77          78         inline void addEdge(int from, int end, int flow, int cap) { 79             edge[ce] = (Edge(end, h[from], flow, cap)); 80             h[from] = ce++; 81         } 82          83         inline void addDoubleEdge(int from, int end, int cap) { 84             addEdge(from, end, 0, cap); 85             addEdge(end, from, cap, cap); 86         } 87          88         Edge& operator [] (int pos) { 89             return edge[pos]; 90         } 91 }MapManager; 92 #define m_begin(g, i) (g).h[(i)] 93 #define m_endpos -1 94  95 int n, m; 96 MapManager g; 97 int s, t; 98 int sum = 0; 99 100 inline void init() {101     readInteger(n);102     readInteger(m);103     g = MapManager(n + m + 3, (n + 1) * (m + 1) * 2);104     s = 0, t = n + m + 1;105     for(int i = 1, a, b; i <= n; i++) {106         readInteger(a);107         readInteger(b);108         g.addDoubleEdge(s, i, a);109         sum += a;110         for(int j = 1, c, d; j <= b; j++) {111             readInteger(c);112             readInteger(d);113             g.addDoubleEdge(i, c + n, d);114         }115     }116     for(int i = 1, a; i <= m; i++) {117         readInteger(a);118         g.addDoubleEdge(i + n, t, a);119     }120 }121 122 int* dis;123 boolean* vis;124 queue<int> que;125 inline boolean bfs() {126     memset(vis, false, sizeof(boolean) * (t + 2));127     que.push(s);128     vis[s] = true;129     dis[s] = 0;130     while(!que.empty()) {131         int e = que.front();132         que.pop();133         for(int i = m_begin(g, e); i != m_endpos; i = g[i].next) {134             if(g[i].cap == g[i].flow)    continue;135             int eu = g[i].end;136             if(vis[eu])    continue;137             vis[eu] = true;138             dis[eu] = dis[e] + 1;139             que.push(eu);140         }141     }142     return vis[t];143 }144 145 int *cur;146 inline int blockedflow(int node, int minf) {147     if((node == t) || (minf == 0))    return minf;148     int f, flow = 0;149     for(int& i = cur[node]; i != m_endpos; i = g[i].next) {150         int& eu = g[i].end;151         if(dis[eu] == (dis[node] + 1) && (f = blockedflow(eu, min(minf, g[i].cap - g[i].flow))) > 0) {152             minf -= f;153             flow += f;154             g[i].flow += f;155             g[i ^ 1].flow -= f;156             if(minf == 0)    return flow;157         }158     }159     return flow;160 }161 162 inline void init_dinic() {163     vis = new boolean[(const int)(t + 3)];164     dis = new int[(const int)(t + 3)];165     cur = new int[(const int)(t + 3)];166 }167 168 inline int dinic() {169     int maxflow = 0;170     while(bfs()) {171         for(int i = s; i <= t; i++)172             cur[i] = m_begin(g, i);173         maxflow += blockedflow(s, inf);174     }175     return maxflow;176 } 177 178 inline void solve() {179     printf("%d\n", sum - dinic());180 }181 182 int main() {183 //    freopen("order.in", "r", stdin);184     init();185     init_dinic();186     solve();187     return 0;188 }