Minimum Spanning Tree on Intersecting Segments

Given (n) line segments ([l_i, r_i]) where each segment (i) has a pair of weights (a_i) and (b_i). An undirected graph (G) is constructed with (n) nodes (one per segment) and no edges initially. For every pair of indices (1 \le i < j \le n), if segment (i) and segment (j) intersect (i.e. if (\max(l_i, l_j) \le \min(r_i, r_j))), an edge is added connecting node (i) and node (j) with weight: [ w_{ij} = a_i + a_j + |b_i - b_j| ]

The task is to compute the sum of the weights of the edges in the Minimum Spanning Tree (MST) of (G). If (G) is not connected, output (-1).

inputFormat

The first line contains an integer (n) (the number of segments). Then (n) lines follow, each containing four integers (l_i), (r_i), (a_i), and (b_i) separated by spaces.

outputFormat

Output a single integer: the sum of the weights in the MST of graph (G), or (-1) if the graph is not connected.

sample

3
1 5 1 2
3 7 2 3
4 9 3 5

11