Chắc hẳn bạn đã nghe tới bài toán Tháp Hà Nội nổi tiếng, nhưng bạn có biết rằng có hẳn một nhà máy chuyên sản xuất những chiếc vòng cho trò chơi tuyệt vời này không? Một ngày nọ, nhà vua ra lệnh cho công nhân của nhà máy phải dựng một tòa tháp cao nhất có thể từ những chiếc vòng đã sản xuất sẵn.

Trong kho của nhà máy có ~n~ chiếc vòng. Chiếc vòng thứ ~i~ có bán kính trong ~a_i~, bán kính ngoài ~b_i~ và chiều cao ~h_i~. Nhiệm vụ là chọn ra một số chiếc vòng và xếp chúng lên nhau sao cho:

• Các bán kính ngoài không tăng dần từ dưới lên trên: chỉ có thể đặt vòng ~j~ lên trên vòng ~i~ nếu ~b_j \le b_i~.
• Vòng bên trên không được lọt vào bên trong vòng bên dưới: chỉ có thể đặt vòng ~j~ lên trên vòng ~i~ nếu ~b_j > a_i~.
• Tổng chiều cao của các vòng được dùng là lớn nhất có thể.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ — số chiếc vòng trong kho.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~a_i~, ~b_i~ và ~h_i~ — bán kính trong, bán kính ngoài và chiều cao của chiếc vòng thứ ~i~.

Kết quả

In ra một số nguyên duy nhất — chiều cao lớn nhất của tòa tháp dựng được.

Ví dụ

Đầu vào:

3
1 5 1
2 6 2
3 7 3

Đầu ra:

6

Đầu vào:

4
1 2 1
1 3 3
4 6 2
5 7 1

Đầu ra:

4

Giải thích: Ở ví dụ thứ nhất, ta lấy cả ba chiếc vòng và xếp theo thứ tự ~3, 2, 1~ từ dưới lên.

Ở ví dụ thứ hai, có thể đặt vòng ~3~ lên vòng ~4~ để được tháp cao ~3~, hoặc đặt vòng ~1~ lên vòng ~2~ để được tháp cao ~4~.

Giới hạn

• ~1 \le n \le 10^5~
• ~1 \le a_i, b_i, h_i \le 10^9~ và ~b_i > a_i~

Đáp án có thể vượt quá phạm vi số nguyên ~32~ bit.

Hãy sắp xếp các vòng theo ~b~ giảm dần (nếu bằng nhau thì theo ~a~ giảm dần) rồi dựng tháp từ dưới lên. Gọi ~f_i~ là chiều cao lớn nhất của một tòa tháp mà vòng ~i~ nằm trên cùng; khi đó ~f_i = h_i + \max f_j~ với ~j~ là những vòng đã xét trước và thỏa mãn ~a_j < b_i~. Sau khi nén các giá trị ~a~, đây đúng là một truy vấn lấy ~\max~ trên tiền tố.