Ở trung tâm của Thung lũng Thủy tinh có một ngôi đền sao bí ẩn, nơi nổi tiếng với bộ sưu tập các tinh thể ma thuật tỏa sáng như những vì sao. Mỗi tinh thể giữ sức mạnh đặc biệt và phát ra ánh sáng rực rỡ chiếu sáng toàn bộ thung lũng, miễn là nó không bị chạm vào.

Nhiệm vụ hàng đêm của người bảo vệ ngôi đền là CHỈ chạm vào các tinh thể nằm trong phạm vi được chỉ định của cư dân thung lũng, trong khi tôn trọng tất cả các yêu cầu của họ. Yêu cầu của mỗi cư dân cho người bảo vệ biết phạm vi tinh thể nào KHÔNG được ngừng tỏa sáng TRƯỚC giờ đi ngủ của họ, vì họ sợ bóng tối.

Người bảo vệ bắt đầu hành trình tại lối vào ngôi đền và phải cẩn thận phối hợp các chuyển động của họ để làm mờ các tinh thể sao cho chúng ngừng tỏa sáng vào đúng thời điểm. Các tinh thể được sắp xếp thành một hàng, cách nhau một mét (tinh thể đầu tiên cách lối vào một mét). Người bảo vệ có thể di chuyển với tốc độ một mét mỗi giây và có thể dừng lại khi cần. Thời gian để người bảo vệ chạm và làm mờ một tinh thể là không đáng kể. Với các yêu cầu của cư dân, người bảo vệ ngôi đền muốn biết số giây tối thiểu cần thiết để hoàn thành tất cả các yêu cầu (người bảo vệ không cần quay lại vị trí bắt đầu).

Dữ liệu vào

• Trong dòng đầu tiên là một số nguyên \(N\) \((1 \le N \le 5000)\), số lượng yêu cầu của cư dân.
• Trong \(N\) dòng tiếp theo là các số nguyên \(l_i, r_i, t_i\) \((1 \le l_i \le r_i \le 10^{18}, 1 \le t_i \le 10^{18})\), đại diện cho giới hạn trái và phải của phạm vi tinh thể và giờ đi ngủ của cư dân, tương ứng.

Dữ liệu ra

• Trong dòng đầu tiên và duy nhất xuất thời gian tối thiểu tính bằng giây cần thiết để người bảo vệ hoàn thành tất cả các yêu cầu.

Chấm điểm

Input 1

3
1 1 1
3 3 5
5 5 3

Output 1

7

Input 2

3
1 2 1
1 1 5
1 3 4

Output 2

6

Input 3

3
6 6 6
8 8 7
9 9 9

Output 3

9

Giải thích ví dụ thứ hai:

Người bảo vệ ngôi đền trước tiên sẽ mất 3 giây để đến tinh thể thứ 3. Sau đó, người đó sẽ đợi 1 giây và làm mờ tinh thể thứ 3. Sau đó, người đó sẽ mất 1 giây để đi đến tinh thể thứ 2 và làm mờ nó. Cuối cùng, người đó sẽ mất 1 giây để đến tinh thể thứ 1 và làm mờ nó. Tổng cộng, hành trình của người đó sẽ kéo dài 6 giây, đó là thời gian tối thiểu cần thiết để hoàn thành tất cả các yêu cầu.