0096. Ravioli

Имя входного файла:	ravioli.in
Имя выходного файла:	ravioli.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

Once the Cook decided to cook ravioli. He bought n packages. But the n was very large so he did not find n packages of the same type in the shop. Soon he discovered that different kinds of ravioli have very different cooking times, for example ravioli called "Daria" should be cooked for 3–5 minutes, but ravioli called "Ravioli" should be cooked for 20–25 minutes. But he has only one big pot to cook ravioli! So he should mix only kinds which allow cooking time t he will select.

Also the Cook has associated a preference number P_i with each package. He wants to select integer time t which will maximize the sum of all preference numbers for packages which allow such cooking time. Help him!

Input file

The first line of the input file contains number of packages n (1 ≤ n ≤ 5⋅ 10⁵). Each of the next n lines contain only three positive integers: t_1i, t_2i and P_i (t_1i ≤ t_2i). They mean that this package allows all cooking times t_1i ≤ t ≤ t_2i and has preference number P_i. All numbers are less than 10⁶.

Output file

Output the maximal value for sum of preference numbers and the selected time t.

Examples:

ravioli.in	ravioli.out
3 3 5 3 5 7 2 20 25 2	5 5

Источник: Petrozavodsk Summer 2003. Opening Contest, Friday, August 22
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати