Do you know the game Flappy Bird, which was once popular in 2014? It is a game where a bird moving forward tries to go as far as possible by repeatedly rising and falling to avoid going off-screen or colliding with pipes.

The bird in the Flappy Bird game is actually a pet bird named 'Anna' raised by Kyojun.

Kyojun and his bird Anna, who live in a two-dimensional world, are playing a game similar to Flappy Bird today. It is a game where Anna earns points equal to the sum of the weights of the line segments she passes while flying through the sky.

This game can be described precisely as follows:

There are $N$ line segments on a two-dimensional plane that are parallel to either the $x$-axis or the $y$-axis. The weight of the $i$-th line segment is $A_i$, and the coordinates of its two endpoints are $(X_{1,i}, Y_{1,i})$ and $(X_{2,i}, Y_{2,i})$ for $0 \le i \le N - 1$.

Anna starts flying from any point on the line $x = 0$ in the $+x$ direction and finishes her flight when she reaches the line $x = W$. However, due to safety concerns, Anna cannot fly lower than $y = 0$ or higher than $y = H$. In other words, Anna can only fly within the region $0 \le x \le W$ and $0 \le y \le H$.

Because Anna flies parallel to the $x$-axis, she cannot change her $y$-coordinate while flying. However, with Kyojun's help exactly once, she can change her $y$-coordinate by rising or falling parallel to the $y$-axis during her flight. Note that Anna's $x$-coordinate does not change during the rising or falling process, and she cannot perform both rising and falling.

The score Anna earns is the sum of the weights of all line segments that share at least one point with Anna's flight path.

For example, suppose $W = 5$, $H = 4$, and $N = 7$ line segments are placed as shown below.

The solid blue lines represent the line segments, and the dotted lines represent Anna's flight path. The number inside the circle is the line segment number, and the signed number represents the weight.

If Anna starts flying at $(0, 1)$, rises from $(2, 1)$ to $(2, 4)$, and then finishes her flight at $(5, 4)$, she passes line segments 0, 1, 2, 4, and 6, earning a score of $(-5) + (-1) + 5 + 3 + (-4) = -2$.

However, if Anna starts flying at $(0, 3.4)$, falls from $(1.6, 3.4)$ to $(1.6, 0.5)$, and then finishes her flight at $(5, 0.5)$, she passes line segments 0, 2, and 5, earning a score of $(-5) + 5 + 1 = 1$.

Given the information about $N$ line segments, write a program to find the maximum score Anna can obtain.

Implementation Details

You must implement the following function:

long long get_max_score(int W, int H, vector<int> A, vector<int> X1,
vector<int> Y1, vector<int> X2, vector<int> Y2)

• This function is called exactly once.
• The size of the integer arrays $A$, $X1$, $Y1$, $X2$, and $Y2$ provided as arguments is $N$. Each element $A[i]$, $X1[i]$, $Y1[i]$, $X2[i]$, and $Y2[i]$ represents $A_i$, $X_{1,i}$, $Y_{1,i}$, $X_{2,i}$, and $Y_{2,i}$ respectively ($0 \le i \le N - 1$).
• This function must return the maximum score Anna can obtain.

You must not execute any input/output functions in any part of the source code you submit.

Constraints

• All numbers given in the input are integers.
• $2 \le W \le 100\,000$
• $1 \le H \le 100\,000$
• $1 \le N \le 250\,000$
• $1 \le X_{i,j} \le W - 1$ ($i \in \{1, 2\}, 0 \le j \le N - 1$)
• $0 \le Y_{i,j} \le H$ ($i \in \{1, 2\}, 0 \le j \le N - 1$)
• $-1\,000\,000\,000 \le A_i \le 1\,000\,000\,000$ ($0 \le i \le N - 1$)
• For all $0 \le i \le N - 1$, $X_{1,i} = X_{2,i}$ or $Y_{1,i} = Y_{2,i}$.
• The length of every line segment is positive. That is, for all $0 \le i \le N - 1$, $(X_{1,i}, Y_{1,i}) \neq (X_{2,i}, Y_{2,i})$.

Subtasks

1. (7 points)

   • $W \le 50$
   • $H \le 50$
   • $N \le 50$

2. (8 points)

   • $W \le 50$
   • $H \le 50$

3. (10 points)

   • $N \le 500$

4. (14 points)

   • $N \le 8\,000$

5. (15 points)

   • $X_{1,i} = X_{2,i}$ ($0 \le i \le N - 1$)

6. (10 points)

   • $Y_{1,i} = Y_{2,i}$ ($0 \le i \le N - 1$)

7. (36 points)

   • No additional constraints.

Examples

Input 1

2 1 2
6 1 0 1 1
-10 1 0 1 1

Output 1

-4

Note 1

Consider the case where $W = 2, H = 1, N = 2, A = [6, -10], X_1 = [1, 1], Y_1 = [0, 0], X_2 = [1, 1], Y_2 = [1, 1]$. The grader calls the following function: get_max_score(2, 1, [6, -10], [1, 1], [0, 0], [1, 1], [1, 1]) = -4 If Anna starts flying at $(0, 1)$ and finishes at $(2, 1)$ without rising or falling, she earns the points for line segments 0 and 1, totaling $6 + (-10) = -4$.

Input 2

5 4 5
1 1 0 1 2
1 2 1 2 2
1 3 1 3 4
1 1 3 4 3
-1 2 1 4 1

Output 2

4

Input 3

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

Output 3

5