MST and Rectangles

Time limit8sMemory limit1024 MB

Summary

Given an N by N matrix updated by Q rectangle additions (mirrored across the diagonal), find the MST cost of the complete graph with edge weights A[i][j].

Level: Hard8 of 10
Topics: Minimum spanning tree, Prefix sum, Union-find
Solved: No attempts yet

Problem

You have a 2D array $A$ of size $N \times N$ . Each cell initially contains 0.

You are also given $Q$ queries of the form $X_1$ $X_2$ $Y_1$ $Y_2$ $W$ , which means you should perform the following operation on $A$ :

For each pair of integers $(i, j)$ where $X_1 \le X_2 < Y_1 \le Y_2$ , $X_1 \le i \le X_2$ , and $Y_1 \le j \le Y_2$ , add $W$ to the values of cells $A[i][j]$ and $A[j][i]$ .

Consider an undirected graph $G$ with $N$ vertices. For each $1 \le i, j \le N$ , there is an edge connecting vertices $i$ and $j$ with cost $A[i][j]$ . Calculate the cost of the minimum spanning tree of $G$ .

Input

The first line contains two integers $N$ and $Q$ .

Each of the next $Q$ lines contains five integers $X_1$ $X_2$ $Y_1$ $Y_2$ $W$ , describing one query.

Output

Print the cost of the minimum spanning tree of $G$ .

Constraints

$1 \le N, Q \le 10^5$
$1 \le X_1 \le X_2 < Y_1 \le Y_2 \le N$
$|W| \le 10^6$
Time limit: 8000 ms. Memory limit: 1024 MB.

Examples3

Example 1
Input
```
5 3
1 1 2 4 10
2 2 3 4 10
3 3 4 4 10
```
Expected output
```
0
```

Example 2

Input

5 5
3 3 4 5 -10
1 2 3 4 20
4 4 5 5 -10
2 2 4 4 -20
1 1 2 4 0

Expected output

-20

Example 3

Input

Expected output

-2