Parçala və hökm et

Mansur yeni kompüter strateji oyunu oynayır. Bu çür oyunlarda əsas tapşırıqlardan biri resursların əldə edilməsidir. Xoşbəxtlikdən bu oyunda inkişaf üçün yalnız bir lazım olan resurs var – bu qızıldır və bir də köməkçi enerji.

Bu oyunda müəyyən sayda qızıl və enerji hasil edən mədənlər var. Bütün mədənlər bir düz xətt üzərində yerləşirlər. Şəxsi mədənləri qorumaq üçün öz uzunluğuna bərabər olan enerji istifadə edən güc sahəsi (mədənləri əhatə edən və həmçinin parçaların sonunda olan parçalar) qurmaq lazımdır.

Mansur bir güc sahəsini elə qurmaq istəyir ki, bu səhə ilə mühafizə olunan mədənlərdən hasil olunan enerji ilə sahəni təchis etmək kifayət etsin, bu mədənlərdən hasil edilən qızıl isə daha çox olsun.

Mansura kömək edin, mühafizə olunan mədənlərdən hasil edilən qızılın maksimal sayını təyin edən proqramı yazın.

Giriş verilənləri

İlk sətirdə mədənlərin sayını ifadə edən yeganə tam $n(1\le n\le 10^5)$ ədədi verilir. Növbəti $n$ sayda sətirin hər birində bir-birindən boşluqla ayrılmış qızılın hasil olunduğu mədənin koordinatlarını və uyğun olaraq hasil edilən enerjini ifadə edən üç $x_i,g_i,d_i(0\le x_i\le 10^9,1\le g_i\le 10^9,1\le d_i\le 10^9)$ tam ədədləri verilir. Bütün $x_i$ qiymətləri fərqlidir və artan ardıcılıqda verilmişdir.

Çıxış verilənləri

Mansurun oyunda hasil edə biləcəyi qızılın maksimal sayını ifadə edən yeganə ədədi verməli.

Nümunələr