SPC 케이크

시간 제한1초메모리 제한1024 MB

요약

오른쪽 변과 위쪽 변에서 맨해튼 거리가 L인 두 격자점 A, B를 골라, 원점에서 그은 두 선분이 자르지 않고 남기는 직사각형 초콜릿 넓이의 합이 최대가 되도록 한다.

문제

SPC(Sogang Premium Cake) 제과점은 직사각형 초콜릿이 올려진 직사각형 모양의 케이크만 판매한다.

Mr. K는 심심하지 않게 케이크 조각을 다음과 같은 방법으로 잘라 먹으려고 한다.

그림과 같이 가로와 세로의 길이가 $W$ , $H$ 인 SPC 케이크를 1사분면 위에 고정한다.
케이크의 꼭짓점을 포함한 오른쪽과 윗변 위의 정수 좌표의 점들 중 두 개( $A$ , $B$ )를 $L = \left|x_A-x_B\right|+\left|y_A-y_B\right|$ 이 되도록 선택한다.
케이크의 왼쪽 아래 꼭짓점 $O(0, 0)$ 으로부터 선분 $\overline{OA}$ , $\overline{OB}$ 를 긋는다.
선분 $\overline{OA}$ , $\overline{OB}$ 에 둘러싸인 케이크 조각을 잘라내어 먹는다. 이 때, Mr. K는 선분으로 잘려진 초콜릿은 먹지 않고 온전히 남아 있는 초콜릿만 먹는다. 선분이 초콜릿을 관통하지 않고 꼭짓점과만 만날 때는 잘리지 않은 것으로 간주한다.
초콜릿은 서로 겹치지 않고, 케이크의 모서리에 닿지 않으며, 그림과 같이 좌표축에 평행하도록 케이크 내부에 놓여 있다.

주치의인 당신은 그가 초콜릿을 얼마나 먹게 될지 궁금해졌다. Mr. K가 케이크를 잘랐을 때 먹을 수 있는 초콜릿 면적 합의 최댓값을 구해보자!

주어진 그림에서 왼쪽과 같이 자를 경우 초콜릿 면적 합은 $7$ 로 최대한 먹을 수 있고, 오른쪽의 경우는 $5$ 만큼밖에 먹지 못한다.

첫째 줄에 정수 $W$ , $H$ , $L$ , $N$ 이 주어진다.

둘째 줄부터 $N$ 개 줄에 정수 $x$ , $y$ , $w$ , $h$ 가 주어진다. $\left(x, y\right)$ 는 초콜릿 조각의 왼쪽 아래 꼭짓점의 좌표, $\left(w, h\right)$ 는 초콜릿 조각의 가로와 세로 길이이다.

Mr. K가 먹을 수 있는 초콜릿 넓이 합의 최댓값을 출력한다.

예제 1

입력

예상 출력