플래피 버드

2014년에 한때 유행한 플래피 버드 게임을 아는가? 새가 앞으로 나아가면서 화면 밖으로 넘어가거나 파이프에 부딪히지 않도록 상승과 낙하를 반복해, 최대한 멀리 가는 게임이다.

플래피 버드 게임에 나오는 새는 사실 교준이가 키우는 애완새 '안나'이다.

이차원 세계에 사는 교준이와 새 안나는 오늘도 플래피 버드와 비슷한 놀이를 한다. 안나가 하늘을 날아다니며 선분들을 지나가면, 그 선분들의 가중치 합만큼 점수를 얻는다.

이 놀이를 정확히 서술하면 다음과 같다.

이차원 평면 위에 $x$축 또는 $y$축과 평행한 $N$개의 선분이 있다. $i$번 선분의 가중치는 $A_i$이고, 두 끝 점의 좌표는 $(X_{1,i}, Y_{1,i})$, $(X_{2,i}, Y_{2,i})$이다. ($0 \le i \le N-1$)

안나는 $x = 0$ 직선 위의 원하는 점에서 $+x$ 방향으로 날기 시작해, $x = W$ 직선 위에 도달하면 날기를 끝낸다. 다만 안전상의 문제로 안나는 $y = 0$보다 낮게 날거나 $y = H$보다 높게 날 수 없다. 즉, 안나는 $0 \le x \le W$, $0 \le y \le H$ 영역에서만 날 수 있다.

안나는 $x$축과 평행하게 날기 때문에 날아가는 도중에는 $y$ 좌푯값을 바꿀 수 없다. 대신 교준이의 도움을 받아, 날아가는 도중에 단 한 번 $y$축과 평행하게 상승하거나 낙하해서 $y$ 좌푯값을 바꿀 수 있다. 상승이나 낙하 과정에서 안나의 $x$ 좌푯값은 변하지 않는다. 상승과 낙하는 둘 다 할 수 없다.

안나의 이동 경로와 하나 이상의 점을 공유하는 모든 선분의 가중치 합이 안나가 얻는 점수이다.

예를 들어, $W = 5$, $H = 4$이고 $N = 7$개의 선분이 아래와 같이 놓여 있다고 하자.

파란색 실선은 선분을, 점선은 안나의 이동 경로를 나타낸다. 원 안의 수는 선분 번호이고, 부호가 있는 수는 가중치이다.

안나가 $(0, 1)$에서 날기 시작하여 $(2, 1)$에서 $(2, 4)$까지 상승한 다음, $(5, 4)$에서 날기를 끝낸다면, 0번, 1번, 2번, 4번, 6번 선분을 지나므로 $(-5)+(-1)+5+3+(-4) = -2$점을 얻는다.

그러나 안나가 $(0, 3.4)$에서 날기 시작하여 $(1.6, 3.4)$에서 $(1.6, 0.5)$까지 낙하한 후 $(5, 0.5)$에서 날기를 끝낸다면, 0번, 2번, 5번 선분을 지나므로 $(-5)+5+1 = 1$점을 얻는다.

$N$개의 선분에 대한 정보가 주어질 때, 안나가 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하라.

• 입력에서 주어지는 모든 수는 정수이다.
• $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)$
• 모든 $0 \le i \le N-1$에 대하여, $X_{1, i} = X_{2, i}$ 또는 $Y_{1, i} = Y_{2, i}$이다.
• 모든 선분의 길이는 양수이다. 즉, 모든 $0 \le i \le N-1$에 대하여, $(X_{1, i}, Y_{1, i}) \ne (X_{2, i}, Y_{2, i})$이다.