分类： 最小割

仔细阅读题意，我们发现，这道题本质上就是一个约束类问题：对于每一株植物，都存在一些植物，需要消灭掉它们才能消灭它。
故而，它就变成了一个这样的问题：存在一些植物，其中的一些要消灭了另外一些之后才能消灭，问收益最大化的方法。
如果我们对每一棵植物建点，然后从一棵植物向它的约束植物连边，那么问题就转化为：一张有向图，每个点都有点权，请选中其中的某些点，使得每个点的后继都在这张图中。
这是一类被称为「最大权闭合子图问题」的问题。这种问题的解决方案是，从源点向正权点连权值为点权的边；从负权点向汇点连权值为点权的绝对值的边。原图中的边流量无穷大。
那么，答案就是总权值减去最小割。

---

下面我们来证明这种建模方式的合法性和最优性。
我们令从源点连出的边被割掉表示不选中这个点，连向汇点的边被割掉表示选中这个点。
那么，最终的结果必然是一个闭合子图。
这是因为，对于这张图的最小割，当你选中一个节点之后，这个点的所有后继负权节点都一定被割掉/选中了（根据割的性质显然）；
这个点的所有后继正权节点都一定不被割/选中了（根据最小割的性质，割掉这些边没有意义）。
并且，任何一个闭合子图的选法都至少可以对应一个割法。
这是因为，对于原图中的某一种连接方法，都可以通过割掉不在其之中的所有负权边和在其之中的所有负权边来使其对应。
同时，根据我们此前的定义，最小割的值意味着没选中的正权点的值与选中的负权点的值的绝对值的和。故而，答案便是正权店的值的和减去最小割的值。
而最小割是要尽量小的，故而最小割可以得到最优答案。

---

PS:
这一题应当考虑死锁情况，想象一个无限攻击力和攻速的豌豆射手。（不考虑连样例都过不了）（但是尽管这样还是能够拿到80分）
具体处理方法就大力上一个拓扑排序即可。把所有需要缩掉的点打个标记，然后令这些点在网络流中不存在。
然而，如果我们直接写一个拓扑排序的话，还是只能得到80分的好成绩——这是因为这张图需要对反图进行拓扑排序。
细想，因为这张图上每一条有向边的终点一旦被删去，那么它的所有前驱也都是不能存在的。
故而，对反图进行拓扑排序找环并删去才能符合题目的要求。

---

#include<iostream>
#include<cstdio>
#include<queue>

const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

int n,m,s,t,nw[1005],dep[1005],val[1005];

struct ee{
	int v;
	int w;
	int nxt;
}e[1000005];
int h[1005],et=-1,in[1005];
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
	++in[U];
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		nw[i]=h[i];
		if(dep[i]>-2){		
			dep[i]=INF;
		}
	}
	q.push(s);
	dep[s]=0;
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;;
				q.push(e[i].v); 
			}
		}
	}
//	printf("%d\n",dep[t]);
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				} 
			}
		}
	}
	return cnt;
}

inline int calc(int X,int Y){
	return X*m+Y+1;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}
inline int srt(){
	for(int i=1;i<=t;++i){
		if(!in[i]){
			q.push(i);
		}
		dep[i]=-2;
	}
	int RT=0,p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		dep[p]=0;
		if(val[p]>0){
			RT+=val[p];
		}
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(!e[i].w){
				if(!--in[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
	return RT;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2,et=-1;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,y,z;
	for(int i=1;i<=n*m;++i){
		scanf("%d",&x);
		val[i]=x;
		x>0?(add(s,i,x),0):(x==0?0:(add(i,t,-x),0));
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d%d",&y,&z);
			add(calc(y,z),i,VERYBIG);
		}
		if(i%m){
			add(i,i+1,VERYBIG);
		}
	}
	int tot=srt();
	printf("%d\n",tot-dinic());
}

int main(){
	init();
	return 0;
}