## Editorial for Thang máy vũ trụ

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const maxk=40000;
maxn=400;
var a:array[1..maxn] of longint;
h,c:array[1..maxn] of integer;
f:array[0..1,0..maxk] of longint;
n:integer;
re:longint;

procedure rf;
var i:integer;
begin
for i:=1 to n do readln(h[i],a[i],c[i]);
end;

procedure sort(l,r:integer);
var i,j:integer; x,y:longint;
begin
i:=l; j:=r; x:=a[(i+j) div 2];
repeat
while a[i]<x do i:=i+1;
while a[j]>x do j:=j-1;
if i<=j then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
y:=h[i]; h[i]:=h[j]; h[j]:=y;
y:=c[i]; c[i]:=c[j]; c[j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

procedure pr;
var i,j,t,k,p:longint;
begin
sort(1,n);
fillchar(f,sizeof(f),0);
f[0,0]:=1;
for i:=1 to n do
begin
t:=i mod 2;
f[t]:=f[1-t];
for j:=1 to c[i] do
begin
p:=h[i]*j;
for k:=p to a[i] do
if f[1-t,k-p]=1 then
f[t,k]:=1;
end;
end;
for i:=a[n] downto 0 do
if f[t,i]=1 then break;
re:=i;
end;

procedure wf;
begin
write(re);
end;

begin
rf;
pr;
wf;
end.

program elevator;
uses    math;
type    e=record
h,a,c:longint;
end;
const   maxH=40040;
maxn=404;
oo=123456789;
fi='';
var     b:array[0..maxn] of e;
f:array[0..maxn,0..maxH] of longint;
n,res:longint;

procedure input;
var     inp:text;
i:longint;
begin
assign(inp,fi);
reset(inp);
for i:=1 to n do
close(inp);
end;

procedure swap(i,j:longint);
var     t:e;
begin
t:=b[i];
b[i]:=b[j];
b[j]:=t;
end;

procedure sort(l,r:longint);
var     p:e;
i,j:longint;
begin
if l>=r then exit;
i:=l;j:=r;
p:=b[random(r-l+1)+l];
repeat
while b[i].a<p.a do inc(i);
while b[j].a>p.a do dec(j);
if i<=j then
begin
if i<j then swap(i,j);
inc(i);dec(j);
end;
until i>j;
sort(l,j);sort(i,r);
end;

procedure dp;
var     i,j,k:longint;
begin
b[0].a:=oo;
for i:=1 to n do
for j:=1 to b[i].a do
begin
//f[i,j]:=-oo;
for k:=0 to b[i].c do
if (j>=k*b[i].h) and (j-k*b[i].h<=b[i-1].a)then
f[i,j]:=max(f[i,j],f[i-1,j-k*b[i].h]+k*b[i].h);
res:=max(res,f[i,j]);
end;
end;

begin
input;
sort(1,n);
dp;
write(res);
end.

#### Code mẫu của RR

{\$R+,Q+,S+}
PROGRAM ELEVATOR;
CONST
fi='';
fo='';
max=40000;
maxn=400;
TYPE
rec=record a:longint; h,c:byte; end;
VAR
n:integer;
k:array[1..maxn] of rec;
d:array[0..max] of integer;
trace:array[0..max] of integer;
kq:longint;
Var
f:text;
i:integer;
Begin
Assign(f,fi); Reset(f);
For i:=1 to n do
with k[i] do
Close(f);
End;
Procedure QuickSort;
Procedure Sort(l,r:integer);
Var
i,j:integer;
x:longint;
tg:rec;
Begin
i:=l; j:=r; x:=k[(l+r) div 2].a;
repeat
while k[i].a<x do inc(i);
while k[j].a>x do dec(j);
if i<=j then
begin
tg:=k[i]; k[i]:=k[j]; k[j]:=tg;
inc(i); dec(j);
end;
until i>j;
if i<r then Sort(i,r);
if l<j then Sort(l,j);
End;
Begin
Sort(1,n);
End;
Procedure Solve;
Var
i,j,l,m:longint;
Begin
kq:=0; d[0]:=1;
For i:=1 to n do
For j:=k[i].c downto 1 do
For l:=k[i].a-j*k[i].h downto 0 do
if (d[l]=1) and (d[l+j*k[i].h]=0) and (trace[l]<>i) then
begin
m:=l+j*k[i].h;
d[m]:=1; trace[m]:=i;
if m>kq then kq:=m;
end;
End;
Procedure WriteOutput;
Var
f:text;
Begin
Assign(f,fo); Rewrite(f);
Writeln(f,kq);
Close(f);
End;
BEGIN
QuickSort;
Solve;
WriteOutput;
END.

#### Code mẫu của ll931110

program ELEVATOR;
const
input  = '';
output = '';
maxn = 400;
maxk = 40000;
type
block = record
h,c,a: longint;
end;
var
free: array[0..maxk] of boolean;
t: array[1..maxn] of block;
n: longint;

procedure init;
var
f: text;
i: longint;
begin
assign(f, input);
reset(f);

for i := 1 to n do readln(f, t[i].h, t[i].a, t[i].c);

close(f);
end;

procedure sort;
var
i,j: longint;
tmp: block;
begin
for i := 1 to n - 1 do
for j := i + 1 to n do
if t[i].a > t[j].a then
begin
tmp := t[i];  t[i] := t[j];  t[j] := tmp;
end;
end;

procedure solve;
var
i,j,k,ss: longint;
begin
fillchar(free, sizeof(free), false);
free[0] := true;

for i := 1 to n do
for j := t[i].a downto 0 do if free[j] then
begin
k := 1;
ss := j + t[i].h;
while (k <= t[i].c) and (ss <= t[i].a) do
begin
free[ss] := true;
ss := ss + t[i].h;
inc(k);
end;
end;
end;

procedure printresult;
var
f: text;
res: longint;
begin
res := maxk;
while not free[res] do dec(res);

assign(f, output);
rewrite(f);
writeln(f, res);
close(f);
end;

begin
init;
sort;
solve;
printresult;
end.

#### Code mẫu của khuc_tuan

import java.io.*;
import java.util.*;

public class Main {

class TT{
public int a, c, h;
}

int k;
TT[] a;

void nhap() throws Exception{
a=new TT[k];
for(int i=0;i<k;++i){
a[i]=new TT();
a[i].h=Integer.parseInt(st.nextToken());
a[i].a=Integer.parseInt(st.nextToken());
a[i].c=Integer.parseInt(st.nextToken());
}
}

void xuly(){
Arrays.sort(a, new Comparator<TT>(){
public int compare(TT a,TT b){
return a.a-b.a;
}
});
TreeSet<Integer> f=new TreeSet<Integer>();
TreeSet<Integer> s=new TreeSet<Integer>();
for(int i=0;i<k;++i){
s.clear();
for(int c=0;c<=a[i].c;++c){
}
while(s.size()>100) s.remove(s.first());
f.clear();
while(s.size()>0){
s.remove(s.first());
}
}
System.out.println(f.last());
}

void run() throws Exception{
nhap();
xuly();
}

public static void main(String[] args) throws Exception{
new Main().run();
}
}