Description

There are $n$ Honkai beasts. Each Honkai beast has five attributes: health, energy, attack, defense, and collapse energy. For the $i$-th Honkai beast, denote these five attributes by their initials as $H_i$, $E_i$, $A_i$, $D_i$, and $C_i$.

Theresa may choose any Honkai beast to attack first. If she kills Honkai beast $i$, she gains $C_i$ cuteness points. Since Theresa gets stronger as she fights, the next Honkai beast $j$ she fights must satisfy $H_j \ge H_i$, $E_j \ge E_i$, $A_j \ge A_i$, and $D_j \ge D_i$.

Please help Theresa compute the maximum total cuteness points she can obtain.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines: on line $i+1$, there are five integers $H_i, E_i, A_i, D_i, C_i$, representing the attribute values of the $i$-th Honkai beast.

Output Format

Output one integer, representing the maximum cuteness points (she must kill at least one Honkai beast). The answer is guaranteed not to exceed the range of long long ($2^{63}-1$).

5
1 9 3 6 233
0 8 3 7 666
-3 9 4 2 810
2 3 3 3 -100
1 8 8 9 603

1269

Hint

For $100\%$ of the testdata, it holds that $1 \le n \le 50000$, and $-10^9 \le H_i, E_i, A_i, D_i, C_i \le 10^9$.

Translated by ChatGPT 5