Maximum Weight Selection of Non‐Overlapping Segments with Different Colors

You are given m line segments. Each segment is described by four positive integers \(l_i, r_i, c_i, w_i\), where \(l_i\) and \(r_i\) denote the endpoints of the segment, \(c_i\) is its color (or type) and \(w_i\) is its weight.

You must select a subset of these segments such that the following condition is satisfied and the total weight is maximized:

• For any two different selected segments \(i\) and \(j\), either \(c_i = c_j\) or \([l_i, r_i] \cap [l_j, r_j] = \varnothing\). In other words, if two segments have different colors then their intervals must not overlap.

Note: There is no restriction on segments of the same color – you may select arbitrarily many of them even if they overlap.

Hint: In any valid solution that uses segments of more than one color, the segments from different colors cannot interlace; all segments from one color must lie completely to the left or to the right of every segment of any other color.

Your task is to compute the maximum possible sum of weights of segments that can be chosen while obeying the constraint above.

inputFormat

The first line contains a single integer \(m\) denoting the number of segments.

Then \(m\) lines follow. Each line contains four positive integers \(l_i\), \(r_i\), \(c_i\) and \(w_i\) separated by spaces, describing a segment.

You may assume that all values are positive integers.

outputFormat

Output a single integer — the maximum total weight of a valid selection of segments.

sample

3
1 3 1 10
4 6 2 20
2 5 1 15

30