Üç öğrenciden oluşan bir takım, sıra dışı bir programlama olimpiyatına katılıyor. Takımın her üyesinin kendi bilgisayarı var, bu yüzden takım aynı anda üç problem üzerinde çalışabilir.
Olimpiyatta problem var. problemi yalnızca bir katılımcı l_i. dakikadan r_i. dakikaya kadar (bu dakikalar dahil) ara vermeden onun üzerinde çalışırsa çözülebilir. Bir dakika boyunca bir katılımcı yalnızca tek bir problem üzerinde çalışabilir ve bir problem birkaç katılımcı arasında bölüştürülemez. Örneğin, bir katılımcı – ve – dakikalarını gerektiren problemleri çözebilir, ancak – ve – dakikalarını gerektiren problemleri çözemez, çünkü her ikisi de . dakikaya ihtiyaç duyar.
problemini çözdüğü için takım w_i puan alır. Takımın elde edebileceği en yüksek toplam puanı bulun.
İlk satırda tek bir tam sayı (1 \le t \le 2 \cdot 10^5) — test durumlarının sayısı verilir.
Her test durumunun ilk satırında tek bir tam sayı (1 \le n \le 2 \cdot 10^5) — problemlerin sayısı verilir.
Sonraki satırın her birinde üç tam sayı l_i, r_i ve w_i (1 \le l_i \le r_i \le 10^9, 1 \le w_i \le 10^9) — probleminin ilk ve son dakikası ile ondan alınacak puan verilir.
Tüm test durumları için değerlerinin toplamının 2 \cdot 10^5 değerini aşmadığı garanti edilir.
Her test durumu için ayrı bir satırda tek bir tam sayı — en yüksek toplam puanı yazdırın.
Örnek 1
Birinci test durumunda dört problemin hepsi . ve . dakikalara ihtiyaç duyar, bu yüzden en fazla üçü çözülebilir. En kârlısı puanlık problemden vazgeçip 3 + 4 + 5 = 12 puan almaktır.
İkinci test durumunda ilk dört problem . dakikaya ihtiyaç duyar, bu yüzden bunlardan birinden vazgeçmek gerekir. En kârlısı üçüncü problemden vazgeçmektir. Diğer dört problem çözülebilir: birinci katılımcı (dakikalar –) ve (dakikalar –) problemlerini, ikincisi problemini, üçüncüsü ise problemini çözer. Toplamda 10 + 1 + 10 + 7 = 28 puan.
Üçüncü test durumunda tek problem çözülebilir.