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

Nhiệm vụ mỗi đêm của người canh đền là chỉ chạm vào các viên pha lê nằm trong những đoạn được người dân chỉ định, đồng thời phải thỏa mãn mọi yêu cầu của họ. Mỗi yêu cầu của một người dân cho biết một đoạn pha lê mà không được tắt sáng trước giờ đi ngủ của người đó, vì họ sợ bóng tối.

Người canh đền bắt đầu hành trình từ cửa vào ngôi đền và phải phối hợp việc di chuyển thật cẩn thận để làm tắt các viên pha lê đúng thời điểm. Các viên pha lê được xếp trên một đường thẳng, cách nhau đúng ~1~ mét (viên đầu tiên cách cửa vào ~1~ mét).

Người canh đền di chuyển với tốc độ ~1~ mét mỗi giây và có thể dừng lại nếu cần. Thời gian để chạm vào và làm tắt một viên pha lê là không đáng kể.

Cho các yêu cầu của người dân, hãy xác định số giây nhỏ nhất cần thiết để người canh đền thực hiện xong mọi yêu cầu.

Người canh đền không cần quay lại vị trí ban đầu sau khi hoàn thành nhiệm vụ.

Hãy tính thời gian nhỏ nhất để người canh đền có thể thực hiện xong sao cho thỏa mãn tất cả các yêu cầu.

Input

• Dòng đầu chứa số nguyên ~N~ ~(1 \le N \le 5000)~ là số lượng yêu cầu của người dân.

• Mỗi dòng trong ~N~ dòng tiếp theo chứa ba 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})~, trong đó ~l_i~ là đầu trái của đoạn pha lê, ~r_i~ là đầu phải của đoạn pha lê, ~t_i~ là giờ đi ngủ của người dân đó.

Output

• In ra trên một dòng duy nhất thời gian nhỏ nhất (tính bằng giây) mà người canh đền cần để thỏa mãn tất cả các yêu cầu.

Scoring

Sample Input 1

3
1 2 1
1 1 5
1 3 4

Sample Output 1

6

Notes

Người canh đền trước tiên mất ~3~ giây để đi tới viên pha lê thứ ~3~.

Sau đó, ông đợi ~1~ giây rồi làm tắt viên pha lê thứ ~3~.

Tiếp theo, ông mất ~1~ giây để đi tới viên pha lê thứ ~2~ và làm tắt nó.

Cuối cùng, ông mất ~1~ giây để đi tới viên pha lê thứ ~1~ và làm tắt nó. Tổng thời gian hành trình là ~6~ giây, và đó là thời gian nhỏ nhất.