记录编号	469249	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2011]聪明的质监员	最终得分	100
用户昵称	ConanQZ	是否通过	通过
代码语言	Pascal	运行时间	0.770 s
提交时间	2017-11-02 20:54:51	内存使用	6.27 MiB

program smart;
const
mn=200000;
type
  node1=record
    w,v:longint;
  end;
  node2=record
    l,r:longint;
  end;
var
arr_num,arr_v:array[0..mn]of int64;
q:array[1..mn]of node2;
a:array[1..mn]of node1;
i,n,m,l,r,mid:longint;
ans1,ans2,k,s:int64;

function min(x,y:int64):int64;
begin
if x<y then exit(x) else exit(y);
end;

procedure make(x:longint);
var
i:longint;
begin
fillchar(arr_num,sizeof(arr_num),0);
fillchar(arr_v,sizeof(arr_v),0);
//if a[1].w>=x then arr_num[1]:=1;
for i:=1 to n do if a[i].w>=x then arr_num[i]:=arr_num[i-1]+1 else arr_num[i]:=arr_num[i-1];
//if a[1].w>=x then arr_v[1]:=a[i].v;
for i:=1 to n do if a[i].w>=x then arr_v[i]:=arr_v[i-1]+a[i].v else arr_v[i]:=arr_v[i-1];
end;

function check(l,r:longint):int64;
var
i:longint;
begin
exit((arr_num[r]-arr_num[l-1])*(arr_v[r]-arr_v[l-1]));
end;

begin
//assign(input,'11.in'); reset(input);
assign(input,'qc.in'); reset(input);
assign(output,'qc.out'); rewrite(output);
  readln(n,m,s);
  for i:=1 to n do
    begin
	 readln(a[i].w,a[i].v);
	 if a[i].w>r then r:=a[i].w;
	end;
  for i:=1 to m do readln(q[i].l,q[i].r);
  l:=1; inc(r);
  while l<r-1 do
    begin
	 mid:=(l+r)>>1;
	 make(mid);
	 k:=0;
	 for i:=1 to m do inc(k,check(q[i].l,q[i].r));
	 if k<s then r:=mid else l:=mid;
	end;
//writeln(l,' ',r);
make(l);
for i:=1 to m do inc(ans1,check(q[i].l,q[i].r));
make(r);
for i:=1 to m do inc(ans2,check(q[i].l,q[i].r));
writeln(min(abs(s-ans1),abs(s-ans2)));
end.