Üç tələbədən ibarət komanda qeyri-adi proqramlaşdırma olimpiadasında iştirak edir. Komandanın hər üzvünün öz kompüteri var, ona görə də komanda eyni vaxtda üç məsələ üzərində işləyə bilər.
Olimpiadada məsələ var. məsələsini yalnız o halda həll etmək olar ki, bir iştirakçı l_i dəqiqəsindən r_i dəqiqəsinə qədər (daxil olmaqla) fasiləsiz onun üzərində işləsin. Bir dəqiqə ərzində iştirakçı yalnız bir məsələ üzərində işləyə bilər, məsələni isə bir neçə iştirakçı arasında bölmək olmaz. Məsələn, bir iştirakçı – və – dəqiqələrini tələb edən məsələləri həll edə bilər, lakin – və – dəqiqələrini tələb edən məsələləri həll edə bilməz, çünki hər ikisinə -cü dəqiqə lazımdır.
məsələsinin həlli üçün komanda w_i bal alır. Komandanın toplaya biləcəyi ən böyük ümumi bal sayını tapın.
Birinci sətirdə bir tam ədəd (1 \le t \le 2 \cdot 10^5) — test hallarının sayı verilir.
Hər test halının birinci sətrində bir tam ədəd (1 \le n \le 2 \cdot 10^5) — məsələlərin sayı verilir.
Sonrakı sətirdən hər birində üç tam ədəd l_i, r_i və w_i (1 \le l_i \le r_i \le 10^9, 1 \le w_i \le 10^9) — məsələsinin birinci və sonuncu dəqiqəsi, həmçinin ona görə verilən balların sayı yerləşir.
qiymətlərinin bütün test halları üzrə cəminin 2 \cdot 10^5 qiymətini aşmadığı təmin edilir.
Hər test halı üçün ayrıca sətirdə bir tam ədəd — ən böyük ümumi bal sayını çıxarın.
Nümunə 1
Birinci test halında hər dörd məsələyə və dəqiqələri lazımdır, ona görə də onlardan ən çoxu üçünü həll etmək olar. Ən sərfəlisi bal dəyərində olan məsələdən imtina edib 3 + 4 + 5 = 12 bal toplamaqdır.
İkinci test halında ilk dörd məsələyə -cü dəqiqə lazımdır, ona görə də onlardan birindən imtina etmək lazım gəlir. Ən sərfəlisi üçüncü məsələdən imtina etməkdir. Qalan dörd məsələni həll etmək olar: birinci iştirakçı (– dəqiqələri) və (– dəqiqələri) məsələlərini, ikinci — məsələsini, üçüncü isə məsələsini həll edir. Cəmi 10 + 1 + 10 + 7 = 28 bal.
Üçüncü test halında yeganə məsələni həll etmək olar.