Protective Tents

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.

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.

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