Flappy Bird

Have you heard of Flappy Bird, the game that was briefly popular in 2014? A bird flies forward and keeps rising and falling so that it does not leave the screen or hit a pipe, going as far as it can.

The bird in Flappy Bird is actually Anna, a pet bird raised by Gyojun.

In a two-dimensional world, Gyojun and Anna are playing a game similar to Flappy Bird. As Anna flies around the sky and passes through line segments, she earns points equal to the sum of the weights of those segments.

Here is a precise description of the game.

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

Anna starts flying in the $+x$ direction from any point on the line $x = 0$, and stops when she reaches the line $x = W$. For safety reasons, however, Anna cannot fly below $y = 0$ or above $y = H$. In other words, Anna can only fly within the region $0 \le x \le W$, $0 \le y \le H$.

Anna flies parallel to the $x$-axis, so she cannot change her $y$ coordinate while flying straight. With Gyojun's help, however, she can change her $y$ coordinate exactly once during the flight by rising or falling parallel to the $y$-axis. Her $x$ coordinate does not change during the rise or fall. Note that she cannot both rise and fall.

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

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

The solid blue lines are the segments, and the dotted line is Anna's path. The number in each circle is the segment number, and the signed number is its weight.

If Anna starts at $(0, 1)$, rises from $(2, 1)$ to $(2, 4)$, and then finishes at $(5, 4)$, she passes segments 0, 1, 2, 4, and 6, so she earns $(-5)+(-1)+5+3+(-4) = -2$ points.

But if Anna starts at $(0, 3.4)$, falls from $(1.6, 3.4)$ to $(1.6, 0.5)$, and then finishes at $(5, 0.5)$, she passes segments 0, 2, and 5, so she earns $(-5)+5+1 = 1$ point.

Given the information about the $N$ segments, write a program that finds the maximum score Anna can earn.

• All numbers 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 every $0 \le i \le N-1$, $X_{1, i} = X_{2, i}$ or $Y_{1, i} = Y_{2, i}$.
• Every segment has a positive length. That is, for every $0 \le i \le N-1$, $(X_{1, i}, Y_{1, i}) \ne (X_{2, i}, Y_{2, i})$.