Елеонор gölü

Məşhur "Eleanor Gölü" qrupu koordinat oxunda konsert keçirir.

Məlumdur ki, konsert keçirilən ölkədə $n$ nəfər yaşayır. $i$-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.

Giriş verilənləri

Birinci sətir bir tam ədəd $n$ ($1\le n\le 200000$) ehtiva edir.

Növbəti $n$ sətirin hər biri üç tam ədəd $x_i$, $w_i$, $d_i$ ($0\le x_i\le 10^9$, $1\le w_i\le 1000$, $0\le d_i\le 10^9$) ehtiva edir.

Çıxış verilənləri

Bir tam ədəd çıxarın — məsələnin cavabı.

Nümunələr

Qiymətləndirmə

1. ($28$ bal): $n,x_i,d_i\le 2000$;

2. ($57$ bal): $x_i,d_i\le 10^6$;

3. ($15$ bal): əlavə məhdudiyyətlərsiz.