bzoj1565

/*
注意topsort的时候还是按照 a保护b a->b来建边
最后跑maxflow才改成b->a
原因:一个有向图所有边反向，有可能原图的环会改变 
*/

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define inf 0x3f3f3f3f
#define ll long long
#define N 605
using namespace std;
int n,m,sum,tot,S,T,sc[N],in[N],ok[N],cur[N],hd[N],vis[N],d[N];
struct edge{int v,next,cap;}e[N*N*2];
vector<int>g[N];queue<int>q;
void adde(int u,int v,int c){
	e[tot].v=v;
	e[tot].next=hd[u];
	e[tot].cap=c;
	hd[u]=tot++;
}
void topsort(){
	for(int i=1;i<T;i++){
		if(!in[i])
		ok[i]=1,q.push(i);
	}
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];--in[v];
			if(!in[v]){
				ok[v]=1;
				q.push(v);
			}
		}
	}
}
bool bfs(){
	memset(vis,0,sizeof(vis));
	d[S]=0;vis[S]=1;q.push(S);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=hd[u];~i;i=e[i].next){
			int v=e[i].v;
			if(e[i].cap&&!vis[v]){
				vis[v]=1;
				d[v]=d[u]+1;
				q.push(v);
			}
		}
	}
	return vis[T];
}
int dfs(int u,int a){
	if(u==T||!a)return a;
	int fl=0,f;
	for(int &i=cur[u];~i;i=e[i].next){
		int v=e[i].v;
		if(e[i].cap&&d[v]==d[u]+1&&(f=dfs(v,min(e[i].cap,a)))){
			fl+=f;a-=f;e[i].cap-=f;
			e[i^1].cap+=f;if(!a)break;
		}
	}
	return fl;
}

int main(){
#ifdef wsy
	freopen("data.in","r",stdin);
#else
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
#endif
	memset(hd,-1,sizeof(hd));
	scanf("%d%d",&n,&m);S=0;T=n*m+1;
	for(int i=1;i<T;i++){
		int c,x,y,id;
		scanf("%d%d",&sc[i],&c);
		for(int j=1;j<=c;j++){
			scanf("%d%d",&x,&y);
			x++;y++;
			id=(x-1)*m+y;
			g[i].push_back(id);
			in[id]++;
		//	printf("%d %d\n",i,id);
		}
		if(i%m)g[i+1].push_back(i),in[i]++/*,printf("%d %d\n",i+1,i)*/;
	}
	topsort();
	for(int i=1;i<T;i++){
		if(!ok[i])continue;
		for(int j=0;j<g[i].size();j++){
			int v=g[i][j];
			if(!ok[v])continue;
			adde(v,i,inf);adde(i,v,0);
		//	printf("%d %d %d\n",i,v,inf);
		}
	}
	for(int i=1;i<T;i++){
		if(sc[i]>0&&ok[i])sum+=sc[i];
		if(sc[i]>0&&ok[i])adde(S,i,sc[i]),adde(i,S,0)/*,printf("%d %d %d\n",S,i,sc[i])*/;
		if(sc[i]<0&&ok[i])adde(i,T,-sc[i]),adde(T,i,0)/*,printf("%d %d %d\n",i,T,-sc[i])*/;
	}
	int flow=0;
	while(bfs()){
		for(int i=S;i<=T;i++)cur[i]=hd[i];
		flow+=dfs(S,inf);
	}
	printf("%d",sum-flow);
	return 0;
}