Protective Tents

Time limit2sMemory limit128 MB

Summary

Given non-overlapping horizontal tents, add horizontal segments above them so that every point of the interval between the leftmost and rightmost endpoints receives downward water.

Level: Hard8 of 10
Topics: Greedy, Intervals, Geometry, Dynamic programming
Solved: No attempts yet

Problem

Subin is a farmer living on a two-dimensional plane. Every crop is planted on the x-axis, where the y-coordinate is 0. Harmful rain will fall tomorrow. The rain falls straight down in a direction parallel to the y-axis; for every real number x, rain falls toward (x, 0).

Subin has installed protective tents above the ground. Each tent is represented by a line segment parallel to the x-axis, and its thickness is ignored. When rain lands on a tent, the water flows toward the nearer of the two endpoints. If the two endpoints are equally far away, the water splits and flows toward both endpoints. Once water reaches an endpoint, it falls straight down again from that point. If two tents share the same endpoint, they behave as one tent.

Each protective tent is given as the segment connecting (b_i, y_i) and (e_i, y_i). Let B be the minimum among all b_i, and let E be the maximum among all e_i. Subin's crops are planted along the interval from (B, 0) to (E, 0). Find the minimum total length of additional protective tents that must be installed so every crop in this interval is protected.

Every additional protective tent must also be parallel to the x-axis, have a positive y-coordinate, have integer-coordinate endpoints, and have positive length.

Input

The first line contains N, the number of protective tents that are already installed. (1 ≤ N ≤ 25)

Each of the next N lines contains b_i, e_i, and y_i, describing one protective tent. (0 ≤ b_i, e_i ≤ 10, 1 ≤ y_i ≤ 100,000)

No two protective tents overlap. They may, however, share endpoints.

Output

Print the minimum possible total length of additional protective tents needed to protect all crops.

Examples5

Example 1
Input
```
2
1 2 1
2 3 1
```
Expected output
```
0
```
Example 2
Input
```
1
1 2 1
```
Expected output
```
0
```
Example 3
Input
```
2
0 2 1
1 4 2
```
Expected output
```
1
```
Example 4
Input
```
4
1 4 10
0 3 3
3 5 1000
5 6 8
```
Expected output
```
2
```
Example 5
Input
```
2
0 1 100
1 3 100
```
Expected output
```
0
```