시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
8 초 1024 MB 10 4 4 40.000%

문제

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 X1 X2 YYW, which means you should perform the following operation on A:

  • For each pair of integers (i, j) where X1 ≤ X2 < Y1 ≤ Yand X1 ≤ i ≤ X2 and Y1 ≤ 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 Q.

The next Q lines contain five integers X1 X2 YYW, 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$

 

예제 입력 1

5 3
1 1 2 4 10
2 2 3 4 10
3 3 4 4 10

예제 출력 1

0

예제 입력 2

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

예제 출력 2

-20

예제 입력 3

6 8
1 3 6 6 3
4 4 6 6 10
3 3 5 6 -8
1 2 5 5 -7
1 2 6 6 -1
1 3 4 5 6
3 5 6 6 7
2 3 6 6 3

예제 출력 3

-2

출처