+ محدودیت زمان: ۴ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
استاد که سخت مشغول طرح سوال برای المپیک فناوری است، فرصت برای طراحی لوگو المپیک فناوری ندارد. او برای زدن ۷ ۸ تیر با یک نشان، از همین موضوع نیز سوال طرح کرده است!
او در هر پرسش به شما $n$ بازه‌ی بسته $[l_1, r_1], [l_2, r_2], \dots [l_n, r_n]$ می‌دهد که زیبایی بازه $i$ام برابر $s_i$ است و می‌پرسد که بیشینه زیبایی ۵-تایی المپیکی که با این بازه‌ها می‌توان ساخت، چیست.
به ۵ بازه‌ی $(a, b, c, d, e)$ ۵-تایی المپیکی گوییم، هرگاه:
- $l_a < l_b < r_a < r_b$
- $l_d < l_e < r_d < r_e$
- $l_c < r_b < l_d < r_c$
زیبایی یک ۵-تایی المپیکی برابر با مجموعه زیبایی ۵ بازه‌ی آن است.
# ورودی
در خط اول ورودی عدد صحیح $t$ که برابر تعداد پرسش‌ها است، می‌آید.
$$1 \le t \le 100,000$$
در خط اول هر پرسش، عدد صحیح $n$ که برابر تعداد بازه‌ها در آن پرسش است، می‌آید.
$$1 \le n \le 500,000$$
در خط $i$ام از $n$ خط بعدی، سه عدد صحیح $l_i$ و $ r_i$ و $s_i$ که به ترتیب نشان‌دهنده‌ی سر و ته و زیبایی بازه‌ی $i$ام هستند، می‌آیند.
$$1 \le l_i \le r_i \le 500,000$$
$$1 \le s_i \le 1,000,000$$
تضمین می‌شود که مجموع $n$ها در همه‌ی پرسش‌ها حداکثر برابر $500,000$ است.
# خروجی
برای هر پرسش، در صورتی که هیچ مجموعه‌ی المپیکی‌ای وجود ندارد عدد $-1$ و در غیر این صورت، بیشینه‌ی زیبایی یک ۵-تایی المپیکی را خروجی دهید.
# مثال
## ورودی نمونه ۱
```
2
5
1 3 1
2 4 2
3 6 3
5 7 4
6 8 5
5
1 3 10
2 4 10
3 5 10
5 7 10
6 8 10
```
## خروجی نمونه ۱
```
15
-1
```
در پرسش اول، بازه‌های $(1, 2, 3, 4, 5)$ تشکیل یک ۵-تایی المپیکی می‌دهند. هیچ ۵-تایی المپیکی دیگری در این پرسش وجود ندارد.
||
|:--------:|
| *بازه‌های پرسش اول - دقت کنید که بعد عمودی نقاط صرفا برای وضوح شکل است.* |
در پرسش دوم، هیچ ۵-تایی المپیکی‌ای وجود ندارد.
## ورودی نمونه ۲
```
1
8
1 4 7
2 5 6
3 6 3
4 7 5
5 8 2
6 9 9
7 10 4
8 11 5
```
## خروجی نمونه ۲
```
32
```
در تنها پرسش این مثال، ۵-تایی $(1, 2, 4, 6, 8)$ بیشترین امتیاز را در میان ۵-تایی‌های المپیکی دارد.