Елеонор gölü#10490
Məşhur "Eleanor Gölü" qrupu koordinat oxunda konsert keçirir.
Məlumdur ki, konsert keçirilən ölkədə nəfər yaşayır. -ci şəxs x_i koordinatında yerləşir, saniyədə w_i şərti vahid sürətlə hərəkət edir və konserti yalnız öz yerindən d_i şərti vahid məsafədə eşidə bilir.
O.E. qrupu konserti keçirəcəkləri tam nöqtəni seçməlidir. Konserti evdən eşitməyən bütün insanlar konsertin keçirildiyi yerə qədər hərəkət etməli olacaqlar ki, onu eşidə bilsinlər (yəni, d_i məsafəsində).
Qrupa elə bir nöqtə tapmağa kömək edin ki, bütün insanların konserti eşidəcəkləri nöqtəyə çatmaq üçün sərf edəcəkləri ümumi vaxtı minimallaşdırsın. Lakin nöqtənin özünü deyil, mümkün olan minimal cəmi çıxarın.
Birinci sətir bir tam ədəd (1 \leq n \leq 200\,000) ehtiva edir.
Növbəti sətirin hər biri üç tam ədəd x_i, w_i, d_i (0 \leq x_i \leq 10^9, 1 \leq w_i \leq 1\,000, 0 \leq d_i \leq 10^9) ehtiva edir.
Bir tam ədəd çıxarın — məsələnin cavabı.
Nümunə 1
Nümunə 2
Nümunə 3
( bal): n, x_i, d_i \leq 2\,000;
( bal): x_i, d_i \leq 10^6;
( bal): əlavə məhdudiyyətlərsiz.