Maximizing Sequence Sum Through Optimal Operation Ordering

You are given a sequence of length \(n\) (1-indexed) initially filled with zeros. There are \(m\) operations. The \(i\)-th operation is described by four integers \(l_i, r_i, x_i, y_i\). When you perform an operation, you update the \(l_i\)-th element of the sequence to \(x_i\) and the \(r_i\)-th element to \(y_i\). Each operation must be performed exactly once, but you are allowed to execute them in any order.

After performing all operations, the final value of an element is determined by the last operation that updates it. Your task is to determine an order of operations such that the sum of all elements in the sequence is maximized. It can be shown that the maximum possible sum is equal to the sum over each index \(j\) from \(1\) to \(n\) of the maximum value that can be assigned to it by any operation updating that position. In other words, if for each index \(j\) we define

[ v_j = \max\Big({x_i ;:; l_i = j} \cup {y_i ;:; r_i = j}\Big), ]

(with \(v_j = 0\) if no operation updates position \(j\)), then the answer is

[ \text{Answer} = \sum_{j=1}^{n} v_j. ]

You need to compute and output this maximum sum.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) \((1 \leq n, m \leq 10^5)\). Each of the next \(m\) lines contains four integers \(l_i, r_i, x_i, y_i\) \((1 \leq l_i, r_i \leq n,\) and the values \(x_i, y_i\) can be any integers). It is guaranteed that each operation updates valid positions in the sequence.

outputFormat

Output a single integer: the maximum possible sum of the sequence after performing all operations in an optimal order.

sample

3 2
1 2 10 1
2 3 5 20

35