Branimirko je još uvijek strastveni igrač svjetski popularne igre Pokémon Go. Nedavno je odlučio organizirati jedno natjecanje u skupljanju Pokémona. To natjecanje će se održati u Ilici u Zagrebu, a glavni sponzor će biti njegov prijatelj Slavko. Nagrada su, naravno, bomboni!

Ilica je, kao što svi znamo, najdulja ulica u Zagrebu. Tamo se nalazi \(N\) kuća sa iste strane ulice, te svaka kuća ima svoj kućni broj između \(1\) i \(N\) . Kućni brojevi poredani su od \(1\) do \(N\) slijeva nadesno. Natjecanje počinje kod kućnog broja \(K\) .

Prije natjecanja Branimirko je pogledao kartu, te je tamo vidio \(M\) Pokémona. Svaki Pokémon se nalazi na svojem (jedinstvenom) kućnom broju \(A_i\) , ima vrijednost \(B_i\) bombona, te se može sakupiti još samo sljedećih \(T_i\) sekundi, nakon čega nestaje s karte i nije ga moguće više pokupiti.

Branimirko može proći jedan kućni broj svake sekunde. Također, kada skupi Pokémona taj Pokémon nestaje s karte.

Kako Branimirko jako voli bombone, zamolio vas je za pomoć. Pomozite mu i recite koliko je najviše bombona moguće zaraditi!

Ulazni​ podaci

U prvom retku nalaze se prirodni brojevi \(N\), \(K\) \(( 1 \leq K \leq N \leq 1 000 )\) i \(M\) \(( 1 \leq M \leq 100 )\), broj kuća, početni kućni broj i broj Pokémona.

U sljedećih \(M\) redaka nalaze se prirodni brojevi \(A_i\) \(( 1 \leq A_i \leq N )\), \(B_i\) \((1 \leq B_i \leq 100 )\) i \(T_i\) \((1 \leq T_i \leq 2 000 )\) iz teksta zadatka.

U ulazu će Pokémoni uvijek biti poredani u strogo rastućem poretku po kućnom broju \(A_i\).

Izlazni podaci

Ispišite traženi maksimalni broj bombona iz teksta zadatka.

Bodovanje

U test podacima vrijednima ukupno \(20 \%\) bodova vrijedit će \(M \leq 10\).

U dodatnim test podacima vrijednima ukupno \(20 \%\) bodova vrijedit će \(M \leq 20\).

Primjeri test​ podataka

Ulaz

10 5 4
1 30 4
3 5 7
7 10 12
9 100 23

Izlaz

115

Objašnjenje

Jedna od strategija je da Branimirko prvo skupi Pokémona na kućnom broju \(3\) (\(5\) bombona), zatim redom na kućnim brojevima \(7\) (\(10\) bombona) i \(9\) (\(100\) bombona) za ukupno \(115\) bombona.

Primijetite da Branimirko ne može skupiti Pokemona na kućnom broju \(1\) jer ne stiže do njega na vrijeme sa svoje početne pozicije (kućni broj \(5\)).

Ulaz

20 8 7
1 35 14
4 57 1
6 32 2
9 94 28
14 78 8
15 8 1
17 55 3

Izlaz

172