## Editorial for Xe buýt

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

uses math;
const fi='';
maxn=100010;
type ar=array[0..maxn] of longint;
var n,xx,yy,mx:longint;
a,b,c,y,d:ar;
col:array[0..maxn] of int64;
re:int64;

procedure rf;
var i:longint;
begin
for i:=1 to n do
begin
y[i]:=b[i]; d[i]:=i;
end;
end;

procedure sort(l,r:longint);
var i,j,x,t:longint;
begin
i:=l; j:=r; x:=y[(i+j) shr 1];
repeat
while y[i]<x do i:=i+1;
while y[j]>x do j:=j-1;
if i<=j then
begin
t:=y[i]; y[i]:=y[j]; y[j]:=t;
t:=d[i]; d[i]:=d[j]; d[j]:=t;
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;

procedure discr;
var i:longint;
begin
sort(1,n);
mx:=1; b[d[1]]:=1;
for i:=2 to n do
begin
if y[i]>y[mx] then
begin
inc(mx);
y[mx]:=y[i];
end;
b[d[i]]:=mx;
end;
end;

procedure sortt(l,r:longint);
var i,j,x,y,t:longint;
begin
i:=l; j:=r; x:=a[(i+j) shr 1]; y:=b[(i+j) shr 1];
repeat
while (a[i]<x) or ((a[i]=x) and (b[i]<y)) do i:=i+1;
while (a[j]>x) or ((a[j]=x) and (b[j]>y)) do j:=j-1;
if i<=j then
begin
t:=a[i]; a[i]:=a[j]; a[j]:=t;
t:=b[i]; b[i]:=b[j]; b[j]:=t;
t:=c[i]; c[i]:=c[j]; c[j]:=t;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sortt(i,r);
if l<j then sortt(l,j);
end;

procedure update(x:longint;val:int64);
begin
while x<=mx do
begin
if val<=col[x] then exit;
col[x]:=val;
x:=x+x and (-x);
end;
end;

function get(x:longint):int64;
var r:int64;
begin
r:=0;
while x>0 do
begin
r:=max(r,col[x]);
x:=x-x and (-x);
end;
exit(r);
end;

procedure pr;
var i:longint; row,x:int64;
begin
re:=0; row:=0; i:=1;
while (a[i]<1) or ((a[i]=1) and (b[i]<1)) do i:=i+1;
while i<=n do
begin
if (i=1) or (a[i]<>a[i-1]) then row:=0;
x:=get(b[i]);
row:=max(row,x)+c[i];
update(b[i],row);
re:=max(re,row);
inc(i);
end;
writeln(re);
end;

begin
assign(input,fi); reset(input);
rf;
discr;
sortt(1,n);
pr;
close(input);
end.


program MBUS;
uses    math;
const   maxn=100005;
fi='';
type    e=record
x,z,dy:longint;
end;
e2=record
v,p:longint;
end;
var     a:array[1..maxn] of e;
col:array[0..maxn] of e2;
bit:array[1..maxn] of int64;
x,y,n,d:longint;
res:int64;

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

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

procedure sortCol(l,r:longint);
var     i,j:longint;
p,t:e2;
begin
if l>=r then exit;
i:=l;j:=r;
p:=col[random(r-l+1)+l];
repeat
while (col[i].v<p.v) do inc(i);
while (col[j].v>p.v) do dec(j);
if i<=j then begin
if i<j then begin
t:=col[i];
col[i]:=col[j];
col[j]:=t;
end;
inc(i);dec(j);
end;
until i>j;
sortCol(l,j);sortCol(i,r);
end;

procedure discrete;
var     i:longint;
begin
sortCol(1,n);
col[0].v:=-1;
for i:=1 to n do begin
if col[i].v<>col[i-1].v then inc(d);
a[col[i].p].dy:=d;
end;
end;

procedure update(i,v:longint);
begin
while i<=d do begin
bit[i]:=max(bit[i],v);
i:=i+i and (-i);
end;
end;

function get(i:longint):longint;
var     t:longint;
begin
t:=0;
while i>0 do begin
t:=max(t,bit[i]);
i:=i-i and (-i);
end;
exit(t);
end;

procedure dp;
var     i:longint;
t:int64;
begin
sortA(1,n);
for i:=1 to n do begin
t:=get(a[i].dy)+a[i].z;
if bit[a[i].dy]<t then
update(a[i].dy,t);
res:=max(res,t);
end;
end;

begin
input;
discrete;
dp;
write(res);
end.


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

#include <iostream>
#include <algorithm>
#include <map>
#define MAXN 100111
#define F first
#define S second
#define _(u) (u&(-u))
#define FOR(i,a,b) for(long i=a; i<=b; i++)
#define FORV(i,v)  for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
using namespace std;

long n,X,Y,bit[MAXN],f[MAXN];
pair<pair<long,long>,long> a[MAXN];
map<long,long> m;

void inp() {
scanf("%ld %ld %ld",&X,&Y,&n);
FOR(i,1,n) {
scanf("%ld %ld %ld",&a[i].F.F,&a[i].F.S,&a[i].S);
if (a[i].F.F<1 || a[i].F.S<1) a[i].S=0;
}

m[1]=1; m[Y]=0;
FOR(i,1,n) m[a[i].F.S]=0;
FORV(i,m) {
typeof(i) j=i; j--;
i->second=j->second+1;
}

FOR(i,1,n) a[i].F.S=m[a[i].F.S];
Y=m[Y];

sort(a+1,a+n+1);
}

long get(long u) {
if (u<=0) return 0;
long v=u-_(u);
return max(bit[u],get(v));
}

void update(long k,long u) {
bit[u]=max(bit[u],k);
long v=u+_(u);
if (v<=n+1) update(k,v);
}

void solve() {
long res=0;
FOR(i,1,n) {
f[i]=get(a[i].F.S)+a[i].S;
update(f[i],a[i].F.S);
res=max(res,f[i]);
}
printf("%ld",res);
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
inp();
solve();
return 0;
}


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

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = 1e-9;
const ll mod = 100000007;
typedef pair<int, int> II;

#define maxn 100005
#define maxe 100005

ll f[maxn];
vector<int> vx, vy;
pair<II, II> P[maxn];

int X, Y, n;

void update(int u, ll x){
for(int i = u; i < maxn; i += i & -i){
f[i] = max(f[i], x);
}
}

ll get(int u){
ll res = 0;
for(int i = u; i > 0; i -= i & -i){
res = max(res, f[i]);
}
return res;
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
gi(X); gi(Y); gi(n);
vx.resize(n + 2); vy.resize(n + 2);
ms(f, 0);
vx[0] = (X); vy[0] = (Y); vx[1] = (1); vy[1] = (1);
int x, y;
ll c, t;

Rep(i, n){
gi(P[i].fi.fi); gi(P[i].fi.se); gi(P[i].se.fi);
vx[i + 2] = (P[i].fi.fi); vy[i + 2] = (P[i].fi.se);
}
P[n] = mp(mp(1, 1), mp(0, 0));
P[n + 1] = mp(mp(X, Y), mp(0, 0));

sort(all(vx)); sort(all(vy)); sort(P, P + n + 2);
ll res;
For(i, 1, n + 1){
y = lower_bound(all(vy), P[i].fi.se) - vy.begin() + 1;
t = get(y);
update(y, t + P[i].se.fi);
if(i == n + 1) res = t + P[i].se.fi;
}

cout << res;
return 0;
}


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

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int x[100010],y[100010],c[100010],tx[100010];
vector< pair<int,int> > a;
vector< pair<int,int> > v[100010];
int n,m,k;

void update(int p,int q)
{
while (p <= 100000)
{
tx[p] = max(tx[p],q);  p += (p & -p);
};
};

int calc(int p)
{
int q = 0;
while (p)
{
q = max(q,tx[p]);  p -= (p & -p);
};
return q;
};

int main()
{
//    freopen("bus.in","r",stdin);
//    freopen("bus.ou","w",stdout);
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= k; i++)
scanf("%d%d%d", &x[i], &y[i], &c[i]);

for (int i = 1; i <= k; i++)
a.push_back(make_pair(x[i],i));
sort(a.begin(),a.end());
x[a[0].second] = 1;  int cc = 1;
for (int i = 1; i < a.size(); i++)
{
if (a[i].first > a[i - 1].first) cc++;
x[a[i].second] = cc;
};

a.clear();
for (int i = 1; i <= k; i++)
a.push_back(make_pair(y[i],i));
sort(a.begin(),a.end());
y[a[0].second] = 1;  cc = 1;
for (int i = 1; i < a.size(); i++)
{
if (a[i].first > a[i - 1].first) cc++;
y[a[i].second] = cc;
};

for (int i = 1; i <= k; i++) v[x[i]].push_back(make_pair(y[i],i));
for (int i = 1; i <= 100000; i++) sort(v[i].begin(),v[i].end());
int ret = 0;
memset(tx,0,sizeof(tx));
for (int i = 1; i <= 100000; i++)
for (int j = 0; j < v[i].size(); j++)
{
int u = v[i][j].first;  int pos = v[i][j].second;
//            cout << i << ' ' << u << ' ' << pos << endl;
int tmp = calc(u);
ret = max(ret,tmp + c[pos]);
update(u,tmp + c[pos]);
};
printf("%d\n", ret);
};


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

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fi first
#define se second
#define pb push_back
#define MP make_pair

const int maxn=100010;

struct Data{
int x,y,z;
};

int cmp(Data a,Data b){
if(a.x==b.x)return a.y<b.y;
else return a.x<b.x;
}

int X,Y,n,nt;
int T[maxn];
Data a[maxn];
long long F[maxn];
long long B[maxn];

int main() {
scanf("%d%d%d",&X,&Y,&n);
Rep(i,n)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
a[n].x=X,a[n].y=Y,a[n].z=0;
++n;
Rep(i,n)T[i]=a[i].y;
sort(T,T+n);
nt=unique(T,T+n)-T;
sort(a,a+n,cmp);
Rep(i,n){
int id=lower_bound(T,T+nt,a[i].y)-T+1;
int id2=id;
long long r=0;
for(;id>0;id&=(id-1))r=max(r,B[id]);
r+=a[i].z;
F[i]=r;
for(;id2<=nt;id2+=id2&(-id2))B[id2]=max(B[id2],r);
}
Ford(i,n-1,0)if(a[i].x==X&&a[i].y==Y){cout<<F[i]<<endl;break;}
return 0;
}