BARICAVN - BARICA
Tác giả: flashmt
Ngôn ngữ: Pascal
const maxn=100010;
var n,k:longint;
x,y,a,d,f:array[1..maxn] of longint;
maxcol:array[0..maxn] of longint;
procedure rf;
var i:longint;
begin
read(n,k);
for i:=1 to n do
begin
read(x[i],y[i],a[i]);
d[i]:=i;
end;
end;
procedure sort(l,r:longint);
var i,j,t,u,v:longint;
begin
i:=l; j:=r; t:=x[(i+j) shr 1]; v:=y[(i+j) shr 1];
repeat
while (x[i]<t) or ((x[i]=t) and (y[i]<v)) do i:=i+1;
while (x[j]>t) or ((x[j]=t) and (y[j]>v)) do j:=j-1;
if i<=j then
begin
u:=d[i]; d[i]:=d[j]; d[j]:=u;
u:=x[i]; x[i]:=x[j]; x[j]:=u;
u:=y[i]; y[i]:=y[j]; y[j]:=u;
u:=a[i]; a[i]:=a[j]; a[j]:=u;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
function max(u,v:longint):longint;
begin
if u>v then max:=u else max:=v;
end;
procedure pr;
var i,t,u,maxrow:longint;
begin
sort(1,n);
for i:=1 to n do f[i]:=-1;
for i:=0 to maxn div 3 do maxcol[i]:=-1;
for t:=1 to n do
if d[t]=1 then break;
f[t]:=a[t]; maxcol[y[t]]:=a[t]; maxrow:=a[t]; inc(t);
while true do
begin
if x[t]=x[t-1] then
begin
if maxrow>=k then
f[t]:=max(f[t],maxrow-k+a[t]);
end;
if maxcol[y[t]]>=k then
f[t]:=max(f[t],maxcol[y[t]]-k+a[t]);
if x[t]=x[t-1] then maxrow:=max(maxrow,f[t])
else maxrow:=f[t];
maxcol[y[t]]:=max(maxcol[y[t]],f[t]);
if d[t]=n then break;
t:=t+1;
end;
writeln(f[t]);
end;
begin
rf;
pr;
end.