카펫

면접 대비

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

요약

최대 세 개의 축에 나란한 직사각형이 주어질 때, 합집합의 넓이를 구한다.

난이도: 쉬움10점 중 3점
유형: 기하, 구현, 수학, 완전 탐색
정답자: 아직 제출이 없습니다

문제

빌 왕자의 새 성에서 가장 화려한 홀은 바닥이 직사각형입니다. 홀의 벽은 각각 남북 방향과 동서 방향으로 뻗어 있습니다. 참모들은 바닥의 일부를 카펫으로 덮자고 제안하면서 구체적인 배치까지 함께 내놓았습니다.

빌 왕자는 주로 넓이(비용과 직결됩니다)에만 관심이 있어서, 제안된 배치에서 카펫이 덮는 바닥의 총 넓이를 알고 싶어 합니다. 카펫이 서로 겹치는 부분은 한 번만 셉니다.

입력

첫째 줄에 세 정수 $K$ , $L$ , $P$ 가 공백으로 구분되어 주어집니다. $K$ 는 카펫의 개수 ( $1 \le K \le 3$ ), $L$ 은 동쪽 벽에서 서쪽 벽까지의 거리 ( $1 \le L \le 10^6$ ), $P$ 는 북쪽 벽에서 남쪽 벽까지의 거리 ( $1 \le P \le 10^6$ )입니다.

이어지는 $K$ 개의 줄에는 각각 카펫 하나를 나타내는 네 정수 $N$ , $S$ , $E$ , $W$ 가 공백으로 구분되어 주어집니다. 카펫의 변은 모두 벽과 평행하며, $N$ , $S$ , $E$ , $W$ 는 각각 카펫의 북쪽·남쪽·동쪽·서쪽 변이 대응하는 벽으로부터 떨어진 거리를 뜻합니다. 카펫끼리는 일부 또는 전부가 겹칠 수 있습니다. 모든 거리는 미터 단위입니다.

출력

카펫이 덮는 바닥의 총 넓이 $S$ 를 제곱미터 단위의 정수 하나로 첫째 줄에 출력합니다.

예제2

예제 1
입력
```
2 8 9
3 3 3 0
5 1 2 4
```
예상 출력
```
20
```
예제 2
입력
```
3 5 5
3 1 1 3
1 3 3 1
3 1 3 1
```
예상 출력
```
3
```