Uolevi pelaa peliä, jossa hänen tehtävänsä on kerätä mahdollisimman suuren arvon edestä kolikoita. Pelissä aloitetaan koordinaateista $(0, 0)$, ja pelaaja voi kulkea vasemmalle tai ylöspäin (kasvavan x tai y-koordinaatin suuntaan). Tiedät jokaisen kolikon arvon ja sijainnin. Kuinka paljon on suurin kolikkojen yhteisarvo, jonka Uolevi voi kerätä?

Syöte

Syötteen ensimmäisellä rivillä on luku $n$, kolikkojen määrä. Seuraavalla $n$:llä rivillä on jokaisella luvut $x_i$, $y_i$ ja $v_i$, joka tarkoittaa että kolikko $i$ sijaitsee koordinaatissa $(x_i, y_i)$ ja sen arvo on $v_i$. Samassa koordinaatissa ei ole ikinä kahta kolikkoa.

Tuloste

Tulosta suurin kolikkojen yhteisarvo jonka Uolevi voi kerätä.

Rajat

• $1 \le n \le 2 \cdot 10^5$
• $0 \le x_i , y_i \le 10^6$
• $1 \le v_i \le 10^9$

Esimerkki

Syöte:

3
1 1 3
2 1 4
2 2 5

Tuloste:

12

Syöte:

3
1 3 1
2 2 1
3 1 1

Tuloste:

1