Три комп'ютери#13079

Три комп'ютери

3 секунди
256 мегабайтів

Команда з трьох студентів бере участь у незвичайній олімпіаді з програмування. Кожен учасник команди має власний комп'ютер, тож команда може працювати над трьома задачами одночасно.

В олімпіаді є задач. Задачу можна розв'язати, лише якщо один учасник працює над нею без перерви з хвилини l_i до хвилини r_i включно. Протягом однієї хвилини учасник може працювати лише над однією задачею, а ділити задачу між кількома учасниками не можна. Наприклад, один учасник може розв'язати задачі, яким потрібні хвилини – та –, але не задачі, яким потрібні хвилини – та –, бо обом потрібна хвилина .

За розв'язану задачу команда отримує w_i балів. Знайдіть найбільшу сумарну кількість балів, яку може отримати команда.

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 2 \cdot 10^5) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить одне ціле число (1 \le n \le 2 \cdot 10^5) — кількість задач.

Кожен із наступних рядків містить три цілі числа l_i, r_i і w_i (1 \le l_i \le r_i \le 10^9, 1 \le w_i \le 10^9) — першу й останню хвилини задачі та кількість балів за неї.

Гарантується, що сума по всіх тестових випадках не перевищує 2 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть в окремому рядку одне ціле число — найбільшу сумарну кількість балів.

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку всім чотирьом задачам потрібні хвилини і , тож розв'язати можна щонайбільше три з них. Найвигідніше відмовитися від задачі, що приносить бали, і отримати 3 + 4 + 5 = 12 балів.

У другому тестовому випадку першим чотирьом задачам потрібна хвилина , тож від однієї з них доведеться відмовитися. Найвигідніше відмовитися від третьої задачі. Інші чотири задачі можна розв'язати: перший учасник розв'язує задачі (хвилини –) і (хвилини –), другий — задачу , а третій — задачу . Разом 10 + 1 + 10 + 7 = 28 балів.

У третьому тестовому випадку єдину задачу можна розв'язати.