Problem description
Jasio ma niebywałe wzięcie u dziewczyn. Umówił się z wieloma z nich na randki i różne dziwne zabawy, których prawdopodobnie i tak nie zrozumiesz, skoro czytasz to zadanie. Problem polega na tym, że Jasio nie jest zbyt rozgarnięty i umawiał się na randki nie bacząc na terminy, a zatem zachodzi ryzyko, że niektóre randki trzeba będzie odwołać. Dla każdej dziewczyny Jasio określił współczynnik lubienia, określający jak bardzo Jasio chce się z tą dziewczyną spotkać. Teraz chciałby wybrać randki, na które pójdzie w taki sposób, aby przedziały czasu trwania randek były parami rozłączne oraz aby zmaksymalizować sumaryczny współczynnik lubienia. Pomóż mu, a może zdradzi Ci sekret jak też mieć takie powodzenie u kobiet.
Napisz program, który: wczyta informacje o zaplanowanych randkach, wyznaczy maksymalny sumaryczny współczynnik lubienia dla randek, na które Jasio może pójść i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę zaplanowanych randek. W kolejnych N wierszach znajdują się opisy kolejnych randek. Opis każdej z nich składa się z trzech liczb naturalnych Si, Ei, Vi, pooddzielanych pojedynczymi odstępami, określających kolejno: początek i koniec przedziału czasu, w którym trwa randka oraz współczynnik lubienia dla dziewczyny, z którą ma się spotkać.
Wyjście
W pierwszym (i jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – maksymalny sumaryczny współczynnik lubienia dla dziewczyn, z którymi ostatecznie Jasio może odbyć swoje randki.
Ograniczenia
1 ≤ N ≤ 200 000, 0 ≤ Si ≤ Ei ≤ 109, 1 ≤ Vi ≤ 109.
Przykład
| Input | Output | |
|
|