Problem description
Bajtazar oraz jego N przyjaciele mieszkają na tej samej prostej ulicy i trenują do Olimpiady Informatycznej Juniorów. Przez brak światłowodu, narzekają oni na słaby internet, więc Bajtazar postanowił wybudować wzmacniacz sygnału internetu przy ich drodze.
Bajtazar wie, że jego i-ty przyjaciel znajduje się początkowo w swoim domu, Di metrów od początku ulicy i jest w stanie przejść jeden metr w Pi sekund w dowolnym kierunku. Przyjaciel ten posiada laptop, który pozwoli mu połączyć się ze wzmacniaczem, jeśli znajdzie się on w odległości co najwyżej Zi od wzmacniacza. Zarówno na początku (niektórzy przyjaciele to rodzeństwo i mieszkają w tym samym domu), jak i podczas ruszania się, kilka osób może się znajdować na tej samej pozycji na ulicy.
Po tym, jak Bajtazar wybierze liczbę całkowitą w i wybuduje wzmacniacz w odległości w metrów od początku ulicy, wyśle wiadomość o nim do wszystkich swoich przyjaciół. Wtedy każdy z przyjaciół zacznie iść wzdłuż ulicy przez minimalną ilość czasu, która pozwoli mu znaleźć się w zasięgu wzmacniacza (innymi słowy, dopóki przyjaciel numer i znajdzie się co najwyżej Zi metrów od w).
Bajtazar chciałby się dowiedzieć, jaka jest najmniejsza możliwa suma czasów, przez którą jego N przyjaciele będą musieli się poruszać, przy optymalnym wyborze w. Nie umie on jednak znaleźć odpowiedzi samemu, więc poprosił Cię o pomoc.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N – liczba przyjaciół Bajtazara.
W każdym z kolejnych N wierszy znajdują się trzy liczby całkowite oddzielone pojedynczymi spacjami: Di, Pi, Zi. Są to odpowiednio: pozycja domu, czas przejścia jednego metra oraz zasięg i-tego przyjaciela.
Wyjście
W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita – minimalny sumaryczny czas, który przyjaciele Bajtazara spędzą na znalezienie się w zasięgu wzmacniacza.
Ograniczenia
1 ≤ N ≤ 200 000.
0 ≤ Di ≤ 109.
1 ≤ Pi ≤ 1 000.
0 ≤ Zi ≤ 109.
Podzadania
| Podzadanie | Warunki | Punkty |
|---|---|---|
| 1 | N, Zi, Di ≤ 2 000 | 26 |
| 2 | Zi, Di ≤ 106 | 60 |
| 3 | brak dodatkowych ograniczeń | 14 |
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
Jeśli wybierzemy w = 0, jedyny przyjaciel Bajtazara nie będzie musiał się w ogóle ruszyć. |
| Wejście | Wyjście | Wyjaśnienie |
|
|
Jednym z optymalnych wyborów na w jest 14. Wtedy pierwszy przyjaciel musi przejść na pozycję 11 (zajmie mu to 4 ⋅ 1 = 4 sekundy) a drugi na pozycję 16 (zajmie mu to 4 ⋅ 4 = 16 sekund), co zajmie sumarycznie 20 sekund. |
| Wejście | Wyjście | |
|
|