Cắt cỏ

Tại vùng đồng bằng phẳng lặng phía Bắc Nhật Bản, một người nông dân trẻ tên là Haruki được giao nhiệm vụ dọn cỏ trên một cánh đồng rộng lớn. Cánh đồng được mô hình hóa thành một trục số một chiều vô cùng dài, và tại mỗi điểm nguyên trên trục số đó, mọc lên những nhánh cỏ.

Ông chủ của Haruki hiện đang đi du lịch, nhưng trước khi rời đi, ông đã để lại \(N\) yêu cầu về các đoạn cỏ cần được cắt. Mỗi yêu cầu mô tả một đoạn liên tục trên trục số, từ điểm \(l_i\) đến \(r_i\), và kèm theo một thời điểm \(t_i\), là thời điểm sớm nhất mà Haruki được phép bắt đầu cắt bất kỳ nhánh cỏ nào thuộc đoạn này. Cắt sớm hơn sẽ làm hỏng rễ, và ông chủ sẽ rất tức giận.

Haruki bắt đầu tại vị trí \(0\) trên trục số vào thời điểm \(0\). Cứ mỗi một đơn vị thời gian, Haruki có thể đi sang trái, phải, hoặc đứng yên và chờ đợi. Vì là một người lão luyện nên thời gian cắt cỏ của anh ấy là không đáng kể và xem như không tốn đơn vị thời gian.

Bạn hãy giúp Haruki tính toán thời gian sớm nhất có thể hoàn thành tất cả yêu cầu --- tức là tất cả những nhánh cỏ thuộc một trong những đoạn được giao đã được cắt.

Input

• Dòng đầu tiên chứa một số nguyên \(N\) \((1 \leq N \leq 5000)\) --- số yêu cầu được giao.
• Mỗi dòng trong \(N\) dòng tiếp theo chứa ba số nguyên \(l_i, r_i, t_i\) \((1 \leq l_i \leq r_i \leq 10^{18},\ 1 \leq t_i \leq 10^{18})\) --- đoạn cần cắt và thời gian sớm nhất được phép bắt đầu cắt.

Output

• Một số nguyên duy nhất --- thời điểm sớm nhất mà Haruki có thể hoàn thành toàn bộ công việc, thỏa mãn tất cả yêu cầu.

Example

3
1 2 1
1 1 5
1 3 4

6

3
6 6 6
8 8 7
9 9 9

9

Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 20 & \(N \leq 18,\ l_i = r_i\ \text{với mọi}\ i\)

2 & 25 & \(l_i = 1\ \text{với mọi}\ i\)

3 & 35 & \(l_i = r_i\ \text{với mọi}\ i\)

4 & 20 & Không có ràng buộc bổ sung

\hline
\endtabular