#include <iostream>

#define MAXN 300
#define MAXV 3000
#define INF 999999999

struct Match{
	int a,b,repeat;
};

const int S=0;
int n,m,v,T,tot,win[MAXN],lose[MAXN],most[MAXN],c[MAXV][MAXV],map[MAXV][MAXV],data[MAXN][MAXN];
int rem[MAXV][MAXV],past[MAXV];
bool vis[MAXV];
struct Match match[MAXV];

inline int MIN(int a,int b)
{
	return a<b?a:b;
}

int aug(int x,int min)
{
	if (x==T)
		return min;
	int i,y,flow;
	for (i=past[x];i<=map[x][0];i++)
	{
		y=map[x][i];
		if (c[x][y]>0 && !vis[y])
		{
			vis[y]=true;
			flow=aug(y,MIN(min,c[x][y]));
			vis[y]=false;
			if (flow>0)
			{
				c[x][y]-=flow;
				c[y][x]+=flow;
				past[x]=i;
				return flow;
			}
		}
	}
	for (i=1;i<=past[x];i++)
	{
		y=map[x][i];
		if (c[x][y]>0 && !vis[y])
		{
			vis[y]=true;
			flow=aug(y,MIN(min,c[x][y]));
			vis[y]=false;
			if (flow>0)
			{
				c[x][y]-=flow;
				c[y][x]+=flow;
				past[x]=i;
				return flow;
			}
		}
	}
	return 0;
}

int maxflow()
{
	int i,now=0,flow;
	for (i=S;i<=T;i++)
		past[i]=1;
	while (1)
	{
		flow=aug(S,INF);
		now+=flow;
		if (flow==0)
			break;
	}
	return now;
}

bool check(int w)
{
	int i,max;
	//check most[]
	for (i=1;i<=n;i++)
		if (most[i]<0)
			return false;
	for (i=1;i<=n;i++)
		c[S][i]=most[i];
	c[S][w]=INF;
	max=maxflow();
	if (max==tot)
		return true;
	return false;
}

void run()
{
	int w,i,j,maxwin=0;
	for (i=0;i<MAXV;i++)
		for (j=0;j<MAXV;j++)
			rem[i][j]=c[i][j];
	for (w=1;w<=n;w++)//get the WINING TEAM
	{
		maxwin=win[w];
		for (i=1;i<=n;i++)
			maxwin+=data[w][i];
		for (i=1;i<=n;i++)
			most[i]=maxwin-win[i];//WIN AT MOST
		for (i=S;i<=T;i++)
			for (j=S;j<=T;j++)
				c[i][j]=rem[i][j];
		if (check(w))
			printf("%d ",w);
		
	}
}

void addEdge(int a,int b,int repeat)
{
	map[a][++map[a][0]]=b;
	map[b][++map[b][0]]=a;
	c[a][b]=repeat;
}

void ini()
{
	int i,j;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d%d",&win[i],&lose[i]);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			scanf("%d",&data[i][j]);
	m=0;
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++)
		{
			m++;
			match[m].a=i;
			match[m].b=j;
			match[m].repeat=data[i][j];
			tot+=data[i][j];
			addEdge(i,m+n,data[i][j]);
			addEdge(j,m+n,data[i][j]);
		}
	v=m+n+1;
	T=v;
	for (i=1;i<=m;i++)
	{
		addEdge(i+n,T,match[i].repeat);
	}
	for (i=1;i<=n;i++)
		addEdge(S,i,0);
}

int main()
{
	freopen("kleague.in","r",stdin);
	freopen("kleague.out","w",stdout);
	ini();
	run();
	return 0;
}