P9594 "Daily OI Round 1" Memory

Given $m$ line segments. Each segment is described by four positive integers $l_i, r_i, c_i, w_i$, where $l_i, r_i$ are the endpoints of the segment, $c_i$ is the type (category) of the segment, and $w_i$ is the weight of the segment. You need to select some segments such that the following condition is satisfied, and the total weight is maximized. - For any two different segments $i, j$, either $c_i = c_j$ holds, or $[l_i, r_i] \cap [l_j, r_j] = \varnothing$.

The first line contains a positive integer $m$, representing the number of segments. The next $m$ lines each contain four positive integers $l_i, r_i, c_i, w_i$, describing the four parameters of a segment, with meanings as stated above.

Output one integer in a single line, representing the maximum total weight that can be obtained.

### Sample Explanation For sample $1$, the selected segments are segments $1, 2, 3$. They are all of the same type, and the total weight is $21$. It can be proven that this selection is optimal. ### Constraints **This problem uses bundled testdata.** |$\text{Subtask}$|Score|$m \le$|$w_i \le$|$c_i \le $|Special Property| | :-----------: | :-------------:|:-----------: | :-----------: | :-----------: | :-----------: | |$0$|$5$|$16$|$10$|$10^9$|None| |$1$|$20$|$2 \times 10^3$|$10^4$|$10^9$|None| |$2$|$20$|$10^5$|$10^4$|$2$|None| |$3$|$20$|$10^5$|$10^4$|$10^9$|A| |$4$|$35$|$10^5$|$10^4$|$10^9$|None| - Special property A: There do not exist distinct positive integers $i, j$ such that $l_i < l_j \leq r_j < r_i$. For all testdata, it is guaranteed that $1 \leq m \leq 10^5$, $1 \leq l_i \leq r_i \leq 10^9$, $1 \leq c_i \leq 10^9$, and $1 \leq w_i \leq 10^4$. Translated by ChatGPT 5