Žygis į kalnus

Ignas planavo švęsti savo gimtadienį su draugais. Deja, užklupusi pandemija ir karantinas sujaukė Igno planus ir jis nusprendė šventės su draugais neorganizuoti.

Laimei, prieš pat Igno gimtadienį epidemiologinė situacija šalyje ženkliai pagerėjo. Pradedant atverti valstybių sienas, pirmiausia buvo leista atnaujinti skrydžius į Bitkalniją, mat joje užsikrėtusiųjų išvis nebuvo. Taigi Ignas suplanavo gimtadienio proga ten nuvykti ir užlipti į aukščiausią Bitkalnijos viršūnę. Lipimui jis pasisamdė gidą.

Kadangi Ignas buvo pirmasis gido klientas po ilgos pertraukos, gidas pasisiūlė prieš nuvesdamas į aukščiausią viršūnę nemokamai nuvesti į kitas pasirinktas viršūnes, jei pasirinkta viršūnė $V$ tenkins šias sąlygas:

• $V$ aukštis bus nemažesnis nei jau aplankytų viršūnių;
• $V$ bus ne toliau nuo aukščiausios Bitkalnijos viršūnės nei jau aplankytos viršūnės.

Ignas, išgirdęs naujienas, labai apsidžiaugė. Pavartęs žemėlapį jis nusprendė, kaip stipriai kiekviena viršūnė jį domina, ir tai įvertino sveikuoju skaičiumi.

Kokią didžiausią kalnų žavesio (dominimo) sumą gali pasiekti gido vedamas Ignas?

Pirmojoje eilutėje pateiktas kalnų skaičius $N$.

Tolimesnėse $N$ eilučių yra po keturis tarpais atskirtus sveikuosius skaičius $x_i$, $y_i$, $h_i$ ir $d_i$ , kurie nusako, kad koordinatėse $(x_i ; y_i)$ yra kalno viršūnė, kurios aukštis $h_i$, ir jos dominimą Ignas įvertino skaičiumi $d_i$.

Išveskite vieną sveikąjį skaičių – didžiausią galimą Igno su gidu įkoptų viršūnių dominimo sumą.

• $2 ≤ N ≤ 100\, 000$
• $-1\, 000 ≤ x_i , y_i ≤ 1\, 000$
• $1 ≤ h_i , d_i ≤ 100\, 000$
• visi kalnai yra skirtingose vietose, bei yra lygiai vienas aukščiausias kalnas.