记录编号	216895	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	Pascal	运行时间	1.117 s
提交时间	2016-01-01 11:59:33	内存使用	48.18 MiB

uses math;
const
maxl=maxlongint div 2;
var
f:array[0..10000,1..1000]of longint;
hash:array[0..10000,1..1000]of boolean;
x,y,count:array[0..10000]of longint;
ko:array[0..10000,1..2]of longint;
n,m,k,i,j,p,l,h,mi:longint;
begin
assign(input,'birda.in');
reset(input);
assign(output,'birda.out');
rewrite(output);
read(n,m,k);
for i:=1 to n do
for j:=1 to m do
f[i,j]:=maxl;

ko[n,1]:=1;ko[n,2]:=m;
for i:=0 to n-1 do
  begin
  read(x[i],y[i]);ko[i,1]:=1;ko[i,2]:=m;
  end;

for i:=1 to k do
  begin
  read(p,l,h);ko[p,1]:=l+1;ko[p,2]:=h-1;inc(count[p]);
  end;
for i:=2 to n do
count[i]:=count[i]+count[i-1];

for i:=1 to n do
  begin
  p:=i-1;
  for j:=ko[p,1] to ko[p,2] do
    begin
    l:=min(j+x[p],m);f[i,l]:=min(f[i,l],f[p,j]+1);
    end;
  for j:=ko[p,1]+x[p] to ko[i,2] do
    begin
    l:=min(j+x[p],m);f[i,l]:=min(f[i,l],f[i,j]+1);
    end;
  for j:=max(ko[p,1],y[p]+1) to ko[p,2] do
  f[i,j-y[p]]:=min(f[i,j-y[p]],f[p,j]);
  end;

for i:=n downto 0 do
  begin
  mi:=maxl;
  for j:=ko[i,1] to ko[i,2] do
  mi:=min(mi,f[i,j]);
  if mi<>maxl then break;
  end;

if i=n then
  begin
  writeln(1);writeln(mi);
  end
else
  begin
  writeln(0);writeln(count[i]);
  end;
close(input);
close(output);
end.