type

  arr=record

    toward,next,cap,cost:longint;

  end;

const

  maxm=;

  maxn=;

var

  edge:array[..maxm]of arr;

  dist,first,sch,a,new,old,p,slack:array[..maxn]of longint;

  chose:array[..maxn]of boolean;

  maxcost,maxflow,n,s,t,tot,esum,i,tt,sum,jj:longint;

function min(x,y:longint):longint;

begin

  if x<y then exit(x);

  exit(y);

end;

procedure add(i,j,k,l:longint);

begin

  inc(esum);

  edge[esum].toward:=j;

  edge[esum].next:=first[i];

  first[i]:=esum;

  edge[esum].cap:=k;

  edge[esum].cost:=l;

end;

procedure addedge(i,j,k,l:longint);

begin

  add(i,j,k,l);

  add(j,i,,-l);

end;

procedure into;

var

  n,m1,m2,i,j,k,cost1,time:longint;

begin

  readln(n,m1,m2);

  fillchar(first,sizeof(first),);

  esum:=-;

  for i:= to m1 do sch[i]:=i;

  tot:=m1;

  for i:= to n do begin

    inc(tot);

    new[i]:=tot;

    inc(tot);

    old[i]:=tot;

  end;

  inc(tot);

  s:=tot;

  inc(tot);

  t:=tot;

  for i:= to n do begin

    read(a[i]);

    inc(sum,a[i]);

  end;

  for i:= to m1 do begin

    read(j,p[i]);

    addedge(s,sch[i],j,);

  end;

  for i:= to n do begin

    addedge(s,old[i],a[i],);

    for j:= to m1 do

      addedge(sch[j],new[i],a[i],p[j]);

    addedge(new[i],t,a[i],);

  end;

  for i:= to m2 do begin

    read(time,cost1);

    for j:= to n-time do

      for k:=j+time+ to n do

        addedge(old[j],new[k],maxlongint,cost1);

  end;

end;

function aug(x,flow:longint):longint;

var

  now,more,i,too,value:longint;

begin

  if x=t then begin

    inc(maxflow,flow);

    inc(maxcost,dist[s]*flow);

    exit(flow);

  end;

 // writeln(x);

  i:=first[x];

  chose[x]:=true;

  now:=;

  while i>= do begin

    too:=edge[i].toward;

    value:=edge[i].cost;

    if (edge[i].cap>) and (not chose[too]) then

      if dist[x]=dist[too]+value then begin

        more:=aug(too,min(edge[i].cap,flow-now));

        dec(edge[i].cap,more);

        inc(edge[i xor ].cap,more);

        inc(now,more);

        if flow=now then exit(flow);

      end

      else

        slack[too]:=min(slack[too],dist[too]+value-dist[x]);

    i:=edge[i].next;

  end;

  exit(now);

end;

function rel:boolean;

var

  i,spent:longint;

begin

  spent:=maxlongint;

  for i:= to tot do

    if not chose[i] then spent:=min(spent,slack[i]);

  if spent=maxlongint then exit(false);

  for i:= to tot do

    if chose[i] then inc(dist[i],spent);

  exit(true);

end;

begin

  readln(tt);

  for jj:= to tt do begin

    sum:=;

    into;

    fillchar(dist,sizeof(dist),);

    maxcost:=;

    maxflow:=;

    repeat

      for i:= to tot do slack[i]:=maxlongint;

      repeat

        fillchar(chose,sizeof(chose),false);

      until aug(s,maxlongint)<=;

    until not rel;

    write('Case ',jj,': ');

    if sum=maxflow then writeln(maxcost)

      else writeln('impossible');

  end;

end.