0096. Ravioli

Input file name:	ravioli.in
Output file name:	ravioli.out
Time limit:	2 s
Memory limit:	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

Source: Petrozavodsk Summer 2003. Opening Contest, Friday, August 22
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version