//By Ceeji
//Date: 2009-4-24
//Type: Network Flow
//Resource: HNSSYZX HAOI test 4 : Problem 3 : Kleague
Program kleague;
Const
   fin='kleague.in';
   fou='kleague.out';
   maxn=25;
   maxfl=1000;
Var
   n,i,j,k,p,bs,qy:longint;
   can:boolean;
   wi,wii:array[1..maxn]of longint;
   di,dii:array[1..maxn]of longint;
   lij:array[1..maxn,1..maxn]of longint;
   f:array[-1..700]of longint;
   c,ci:array[-1..700,-1..700]of longint;
   d:array[1..maxfl]of longint;
   df:array[1..maxfl]of longint;
   dm:array[1..maxfl]of longint;
   b:array[-1..maxfl]of boolean;
Procedure init;
var i,j:longint;
begin
   assign(input,fin);  reset(input);
   assign(output,fou); rewrite(output);
   readln(n);
   for i:=1 to n do
   begin
      read(wi[i],di[i]);
   end;
   readln;
   for i:=1 to n do
     for j:=1 to n do
       read(lij[i,j]);
   close(input);
end;

Function doit1:boolean;
var i,k:longint;
begin
   i:=1; j:=2; d[1]:=0; df[1]:=-2; dm[1]:=maxlongint;
   fillchar(b,sizeof(b),0);
   repeat
      for k:=-1 to n+bs do
      begin
         if (c[d[i],k]>0)and(b[k]=false) then
         begin
            b[k]:=true;
            d[j]:=k;
            df[j]:=i;
            dm[j]:=dm[i];
            if c[d[i],k]<dm[j] then dm[j]:=c[d[i],k];
            if k=-1 then exit(true);
            inc(j);
         end;
      end;
      inc(i);
   until i>=j;
   exit(false);
end;

Procedure doit2;
var k,an:longint;
begin
   k:=j; an:=dm[j];
   while k<>1 do
   begin
      dec(c[d[df[k]],d[k]],an);
      inc(c[d[k],d[df[k]]],an);
      k:=df[k];
   end;
end;

begin
   init; bs:=0;
   for p:=1 to n do
   begin
      bs:=0; qy:=0;
      fillchar(c,sizeof(c),0);
      for i:=1 to n do
      begin
         for j:=i+1 to n do
         begin
            if (i=p)or(j=p) then begin inc(qy,lij[i,j]); continue; end;
            if lij[i,j]=0 then continue;
            inc(c[0,i],lij[i,j]);
            inc(c[0,j],lij[i,j]);
            inc(bs);
            c[i,n+bs]:=lij[i,j];
            c[j,n+bs]:=lij[i,j];
            c[n+bs,-1]:=lij[i,j];
            ci[n+bs,-1]:=lij[i,j];
         end;
      end;
      can:=true;
      for i:=1 to n do
      begin
         if wi[p]+qy<wi[i] then begin can:=false; break; end;
      end;
      if can then while doit1 do doit2;
      if can then
      for i:=1 to bs do
      begin
        if c[n+i,-1]<>0 then begin can:=false; break; end;
      end;
      if can then write(p,' ');
   end;
   writeln;
   close(output);
end.