Məsələlər
Parçala və hökm et
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.
\InputFile
İ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.
\OutputFile
Mansurun oyunda hasil edə biləcəyi qızılın maksimal sayını ifadə edən yeganə ədədi verməli.
Giriş verilənləri #1
4 0 5 1 1 7 2 4 4 1 7 15 1
Çıxış verilənləri #1
16