Maximise Score

 You are given 

N$N$ segments where each segment is of the form [Li,Ri]$[L_i,R_i]$ (1≤Li≤Ri≤N)$(1\le L_i\le R_i\le N)$.

It is ensured that for any two segments X$X$ and Y$Y$, one of the following conditions hold true:

• X∩Y=X$X\cap Y=X$,
• X∩Y=Y$X\cap Y=Y$, or
• X∩Y=∅$X\cap Y=\mathrm{\varnothing }$ (empty set)

Note that ∩$\cap$ denotes the intersection of segments.

In other words, for any two segments, either one is completely inside the other or they are completely disjoint.

The ith$i^{th}$ segment (1≤i≤N)$(1\le i\le N)$ is assigned a value Vi$V_i$.
A subset S={S1,S2,…,Sk}$S=\{S_1,S_2,\dots ,S_k\}$ having k$k$ segments is considered good if there exists an integer array B$B$ of size k$k$ such that:

• All elements of the array B$B$ are distinct.
• Bi$B_i$ lies in the segment Si$S_i$.

Let the score of a good subset be defined as the sum of values of all segments of the subset. Find the maximum score of a good subset.

Input Format

• The first line of input contains a single integer T$T$ - the number of test cases. The description of T$T$ test cases follow.
• The first line of each test case contains integers N$N$ - the number of segments.
• Each of the next N$N$ lines contains three integers Li,Ri,$L_i,R_i,$ and Vi$V_i$, describing the ith$i^{th}$ segment.

Output Format

For each test case, output the maximum score of a good subset.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤N≤105$1\le N\le {10}^5$
• 1≤Li≤Ri≤N$1\le L_i\le R_i\le N$
• 1≤Vi≤109$1\le V_i\le {10}^9$
• Sum of N$N$ over all test cases does not exceed 3⋅105$3\cdot {10}^5$.

Sample Input 1 

2
4
2 2 5
2 2 10
3 3 14
3 3 20
4
1 3 4
2 3 5
1 1 10
1 4 13

Sample Output 1 

30
32

Explanation

Test case 1$1$: A possible value of good subset is S=[A2,A4]$S=[A_2,A_4]$. The array B=[2,3]$B=[2,3]$ such that 2$2$ lies in the segment A2$A_2$ and 3$3$ lies in the segment A4$A_4$. The sum of values of all segments of S$S$ is 10+20=30$10+20=30$.
It can be proven that the score of a good subset does not exceed 30$30$ in this case.

Test case 2$2$: We can take S=[A1,A2,A3,A4]$S=[A_1,A_2,A_3,A_4]$. The array B=[2,3,1,4]$B=[2,3,1,4]$.

• For segment A1$A_1$, L=1$L=1$ and R=3$R=3$. Here L1≤2≤R1$L_1\le 2\le R_1$.
• For segment A2$A_2$, L=2$L=2$ and R=3$R=3$. Here L2≤3≤R2$L_2\le 3\le R_2$.
• For segment A3$A_3$, L=1$L=1$ and R=1$R=1$. Here L3≤1≤R3$L_3\le 1\le R_3$.
• For segment A4$A_4$, L=1$L=1$ and R=4$R=4$. Here L4≤4≤R4$L_4\le 4\le R_4$.

The sum of scores of all segments of S$S$ is 4+5+10+13=32$4+5+10+13=32$. It can be proven that the score of a good subset does not exceed 4+5+10+13=32$4+5+10+13=32$ in this case.