Problem Description

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

Input Format

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 Format

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

5
2 9 1 1
3 9 1 10
4 8 1 10
5 6 3 1
7 9 3 10

21

10
1 2 2 8
2 4 2 2
6 10 3 5
2 8 2 4
5 9 2 7
1 1 1 10
2 8 2 2
1 7 3 7
8 9 2 4
5 7 3 3

29

Hint

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.

• 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