Üç kompüter#13079

Üç kompüter

3 saniyə
256 meqabayt

Üç 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.

Giriş

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.

Çıxış

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ələr

Nümunə 1

Loading
Loading

Qeyd

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.