17462번 - MST and Rectangles 다국어

문제

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₁ X₂ Y₁ Y₂ W, which means you should perform the following operation on A:

• For each pair of integers (i, j) where X₁ ≤ X₂ < Y₁ ≤ Y₂ and X₁ ≤ i ≤ X₂ and Y₁ ≤ j ≤ Y₂ , add W to the value of cell A[i][j] and A[j][i].

Consider an undirected graph G with N vertices. For each 1 ≤ i, j ≤ N, there is an edge connecting vertices i and j with cost A[i][j]. Calculate the cost of Minimum Spanning Tree of G.

입력

The first line contains a single integer N, Q.

The next Q lines contain five integers X₁ X₂ Y₁ Y₂ W, describing a query.

출력

Print the cost of Minimum Spanning Tree of G.

제한

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

힌트