问题 B: King's Ruins

The first king of Byteland was buried with his $n$ knights a thousand years ago. In the ruins, the archaeologists have found $n$ stone tablets in a row, labeled by $1,2,\dots ,n$ from left to right. Each stone tablet belongs to a knight. On the surface of the $k$-th stone tablet, five numbers are describing the ability of the $k$-th knight in five aspects:

• The wind ability $w$, denoting how fast the knight is.
• The guard ability $g$, denoting how many attacks can be defended by the knight.
• The ice ability $i$, denoting the power of ice crystal cast by the knight.
• The flame ability $f$, denoting the power of fire cast by the knight.
• The light ability $l$, denoting the power of thunder cast by the knight.

Little Q is visiting the stone tablets from left to right, according to the labels from 1 to $n$. After visiting a stone tablet, before moving right to the next one, he can choose to take a photo with it or do nothing. Little Q estimates the value of each stone tablet, he wants to maximize the total value that he takes photos with, and the knight corresponding to the next photo is always not weaker than the current one. Here the $x$-th knight is considered not to be weaker than the $y$-th knight if and only if wx≥wy, gx≥gy, ix≥iy, fx≥fy and lx≥ly.

There are so many stone tablets that Little Q can not determine which to take photos with. Please write a program to help him.

The first line contains a single integer $T$ ($1\le T\le 5$), the number of test cases. For each test case:

The first line contains a single integer $n$ ($1\le n\le 50,000$), denoting the number of stone tablets.

In the next $n$ lines, the $k$-th line contains six integers wk, gk, ik, fk, lk and vk (1≤wk,gk,ik,fk,lk≤n, 1≤vk≤10,000), describing the $k$-th stone tablet, vk denoting the value of the photo with it.

1
4
1 2 1 2 1 30
2 1 2 1 2 40
3 3 3 3 3 50
2 3 3 2 4 100

30
40
90
140