Xəzinə axtaranlar#5529
Uzun axtarışlardan sonra xəzinə axtaranlar, hərəsində qızıl olan nöqtədən ibarət böyük bir sahə kəşf etdilər. Rəhbərin xəritəsində hər xəzinənin koordinatları və oradakı qızılın miqdarı göstərilib. Sahə, ordinatları müsbət olan düzbucaqlı koordinat müstəvisinin nöqtələri toplusundan ibarətdir. Xəzinə axtaranların düşərgəsi oxu boyunca yerləşir. Xəzinə nöqtələrinin koordinatları tam ədədlərdir.
Rəhbərin gizli bir planı var: o, sahənin istənilən tam koordinatlı nöqtəsindən başlayaraq düşərgəyə doğru hərəkət edəcək. Başqalarının diqqətini çəkməmək üçün rəhbər, hər bir nöqtəsindən yalnız bunların birinə — (x-1, y-1), (x, y-1) və ya (x+1, y-1) keçə bilər. Xəzinə olan nöqtədən keçərkən, oradakı bütün qızılı səssizcə götürəcək. Rəhbər oxuna çatdıqda dayanacaq. Bu plan üzrə rəhbərin toplaya biləcəyi maksimum qızıl miqdarını tapın.
Birinci sətirdə tam ədəd (3 \leq N \leq 50000) verilir. Sonra gələn sətrin hər birində -ci xəzinənin koordinatları və oradakı qızılın miqdarı olan x_i, y_i, c_i ədədləri verilir. Hər xəzinənin koordinatı -1000000000 \leq x \leq 1000000000 şərtini ödəyir. Hər xəzinənin koordinatı isə 1 \leq y \leq 1000000000 şərtini ödəyir. Hər bir xəzinədəki qızıl miqdarı [1, 10^9] diapazonunda tam ədəddir.
Çıxışa rəhbərin toplaya biləcəyi maksimum qızıl miqdarını göstərən tək tam ədəd yazın.
Nümunə 1