P5621 [DBOI2019] Theresa Is the Cutest in the World

>As everyone knows, Theresa is the cutest in the world. > >——zhengrunzhe You are playing Honkai Impact 3, and suddenly your parents come in, so you pretend you are working on a data structure problem. 

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.

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 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$).

| Subtask ID | $n \le$ | Score | |:-:|:-:|:-:| | $1$ | $100$ | $20$ | | $2$ | $10^4$ | $20$ | | $3$ | $5 \times 10^4$ | $60$ | 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