{
ID:LXYXYNT
PROB:kleague
LANG:PASCAL
}
const
  inf='kleague.in';
  ouf='kleague.out';
  maxn=25;
  maxm=1000;
    
var   
  left:array[1..maxn,1..maxn]of longint;
  c,ci:array[-1..maxm,-1..maxm]of longint;
  f,d,mini,rec:array[-1..maxm]of longint;
  b:array[-1..maxm] of boolean;
  wi,di:array[1..maxn]of longint;
  n,i,j,k,p,nn,qy:longint;
  bi:boolean;

function doit:boolean;
var
  i,k:longint;
begin
  i:=1; 
  j:=2;
  d[1]:=0; 
  rec[1]:=-2; 
  mini[1]:=maxlongint;
  fillchar(b,sizeof(b),0);
  repeat
    for k:=-1 to n+nn do
    begin
      if (c[d[i],k]>0) and (b[k]=false) then
      begin
        b[k]:=true;
        d[j]:=k;
        rec[j]:=i;
        mini[j]:=mini[i];
        if c[d[i],k]<mini[j] then mini[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,dalta:longint;
begin
  k:=j;
  dalta:=mini[j];
  while k<>1 do
  begin
    dec(c[d[rec[k]],d[k]],dalta);
    inc(c[d[k],d[rec[k]]],dalta);
    k:=rec[k];
  end;
end;

begin
  assign(input,inf);reset(input);
  assign(output,ouf);rewrite(output);
  readln(n);
  for i:=1 to n do read(wi[i],di[i]);
  readln;
  for i:=1 to n do
   for j:=1 to n do
    read(left[i,j]);  
  for p:=1 to n do
  begin
    nn:=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,left[i,j]); continue; end;
        if left[i,j]=0 then continue;
        inc(c[0,i],left[i,j]);
        inc(c[0,j],left[i,j]);
        inc(nn);
        c[i,n+nn]:=left[i,j];
        c[j,n+nn]:=left[i,j];
        c[n+nn,-1]:=left[i,j];
        ci[n+nn,-1]:=left[i,j];
      end;
    end;
    bi:=true;
    for i:=1 to n do
     if wi[p]+qy<wi[i] then 
     begin
       bi:=false; 
       break; 
     end;
    if bi then while doit do doit2;
    if bi then
     for i:=1 to nn do
      if c[n+i,-1]<>0 then
      begin
        bi:=false;
        break;
      end;
    if bi then write(p,' ');
  end;
  writeln;
  close(input);
  close(output);
end.