cho.sh

플래피 버드

아직 제출이 없습니다시간 제한4초메모리 제한1024 MB

문제

여러분은 2014년에 한때 유행한 플래피 버드라는 게임을 아는가? 앞으로 전진하는 새가 화면 밖으로 넘어가거나 파이프에 충돌하지 않도록 상승과 낙하를 반복하면서 최대한 멀리 나아가는 게임이다.

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

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

이 놀이를 엄밀하게 서술하면 다음과 같다.

이차원 평면 위에 xx축 또는 yy축과 평행한 NN개의 선분이 있다. ii번 선분의 가중치는 A_iA\_i이고, 두 끝 점의 좌표는 (X_1,i,Y_1,i)\left( X\_{1, i}, Y\_{1, i} \right), (X_2,i,Y_2,i)\left( X\_{2, i}, Y\_{2, i} \right)다. (0≤i≤N−1)(0 \le i \le N-1)

안나는 x=0x = 0 직선 위 원하는 점에서부터 +x+x 방향으로 날기를 시작하고, x=Wx = W 직선 위에 도달하면 날기를 종료한다. 그러나 안전상의 문제로, 안나는 y=0y = 0보다 낮게 날거나 y=Hy = H보다 높게 날 수는 없다. 즉, 안나는 0≤x≤W0 \le x \le W, 0≤y≤H0 \le y \le H 영역에서만 날 수 있다.

안나는 xx축과 평행하게 날기 때문에 나는 도중에는 자신의 yy 좌푯값을 바꿀 수 없다. 그러나 단 한 번 교준이의 도움을 받아 나는 도중에 yy축에 평행하게 상승 또는 낙하하여 yy 좌푯값을 바꿀 수 있다. 상승 및 낙하 과정에서 안나의 xx 좌푯값은 변하지 않으며, 상승과 낙하 둘 다 할 수는 없음에 유의하라.

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

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

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

만약 안나가 (0,1)(0, 1)에서 날기 시작하고, (2,1)(2, 1)에서 (2,4)(2, 4)까지 상승한 다음, (5,4)(5, 4)에서 날기를 마친다면, 0번, 1번, 2번, 4번, 6번 선분을 지나므로 (−5)+(−1)+5+3+(−4)=−2(-5)+(-1)+5+3+(-4) = -2점의 점수를 얻는다.

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

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

제한

  • 입력에서 주어지는 모든 수는 정수이다.
  • 2≤W≤100,0002 \le W \le 100\\,000
  • 1≤H≤100,0001 \le H \le 100\\,000
  • 1≤N≤250,0001 \le N \le 250\\,000
  • 1≤X_i,j≤W−11 \le X\_{i, j} \le W-1 (i∈1,2,0≤j≤N−1)(i \in \\{ 1, 2 \\}, 0 \le j \le N-1)
  • 0≤Y_i,j≤H0 \le Y\_{i, j} \le H (i∈1,2,0≤j≤N−1)(i \in \\{ 1, 2 \\}, 0 \le j \le N-1)
  • −1,000,000,000≤A_i≤1,000,000,000-1\\,000\\,000\\,000 \le A\_i \le 1\\,000\\,000\\,000 (0≤i≤N−1)(0 \le i \le N-1)
  • 모든 0≤i≤N−10 \le i \le N-1에 대하여, X_1,i=X_2,iX\_{1, i} = X\_{2, i} 또는 Y_1,i=Y_2,iY\_{1, i} = Y\_{2, i}.
  • 모든 선분의 길이는 양수이다. 즉, 모든 0≤i≤N−10 \le i \le N-1에 대하여, (X_1,i,Y_1,i)≠(X_2,i,Y_2,i)\left( X\_{1, i}, Y\_{1, i} \right) \ne \left( X\_{2, i}, Y\_{2, i} \right).