blistavost — COCI CONTEST_#2
Task type: batch | Time limit: 4 s | Memory limit: 1024 MB | Difficulty: 21
Algorithms: dynamic programming

# Task Blistavost

In the heart of the Glass Valley lies a mysterious star temple, a place known for its collection of magical crystals that shine like stars. Each crystal holds special power and emits a radiant glow that illuminates the entire valley, as long as it remains untouched.

The temple guardian's nightly task is to touch ONLY the crystals located within the specified ranges of the valley's residents, while honoring all of their requirements. Each resident's request tells the guardian which range of crystals must NOT stop shining BEFORE their bedtime, as they fear the darkness.

![](./_page_0_Picture_6.jpeg)

The guardian starts his journey at the temple entrance and must carefully coordinate their movements to dim the crystals such that they stop shining at the correct moment. The crystals are arranged in a line, spaced one meter apart from each other (the first crystal is one meter away from the entrance). The guardian can move at a speed of one meter per second and may stop when needed. The time it takes for the guardian to touch and dim a crystal is negligible. Given the residents' requests, the temple guardian wants to know the minimum number of seconds required to fulfill all requests (the guardian does not need to return to the starting position).

## Input

In the first line is an integer $N$ ($1 \leq N \leq 5000$), number of residents' requests.

In the next $N$ lines are integers $l_i, r_i, t_i$ ($1 \leq l_i \leq r_i \leq 10^{18}, 1 \leq t_i \leq 10^{18}$), representing the left and right bounds of the crystal range and the resident's bedtime, respectively.

## Output

In the first and only line output the minimum time in seconds required for the guardian to fulfill all the requests.

## Scoring

| Subtask | Points | Constraints                                      |
|---------|--------|--------------------------------------------------|
| 1       | 20     | $n \leq 18, l_i = r_i \text{ for all } i = 1, 2, ..., n$ |
| 2       | 25     | $l_i = 1 \text{ for all } i = 1, 2, ..., n$           |
| 3       | 55     | $l_i = r_i \text{ for all } i = 1, 2, ..., n$         |
| 4       | 20     | No additional constraints.                           |

## Examples

| input | input | input |
|---|---|---|
| 3 <br> 1 1 1 <br> 3 3 5 <br> 5 5 3 | 3 <br> 1 2 1 <br> 1 1 5 <br> 1 3 4 | 3 <br> 6 6 6 <br> 8 8 7 <br> 9 9 9 |
| output | output | output |
| 7 | 6 | 9 |

![](./_page_1_Picture_0.jpeg)

## Clarification of the second example:

The temple guardian will first take 3 seconds to reach the 3rd crystal. Then, he will wait for 1 second and dim the 3rd crystal. After that, he will take 1 second to go to the 2nd crystal and dim it. Finally, he will take 1 second to reach the 1st crystal and dim it. In total, his journey will last 6 seconds, which is the minimum time required to fulfill all the requests.

Starter code: