투명한 모자이크

면접 대비

시간 제한2초메모리 제한128 MB

요약
100x100 격자에 N개의 사각형 종이를 덮을 때, M장보다 많이 덮인 칸의 개수를 구합니다.
난이도

쉬움10점 중 3점

유형
배열, 시뮬레이션, 완전 탐색
정답자
아직 제출이 없습니다

문제

세준이는 1×1 크기의 작은 그림 100×100개로 이루어진 모자이크 그림을 가지고 있다. 어느 날 모자이크의 일부가 마음에 들지 않아 N장의 불투명한 종이로 그림을 가리기 시작했다.

하지만 한 칸 위에 종이가 조금만 덮여 있다고 해서 항상 보이지 않는 것은 아니다. 어떤 칸 위에 올려진 종이가 M장 이하이면 그 칸의 그림은 보인다. 종이가 M장보다 많이 올려진 칸만 보이지 않는다.

각 종이는 왼쪽 아래 모서리 좌표와 오른쪽 위 모서리 좌표로 주어지며, 종이가 덮는 영역에는 두 모서리의 좌표도 포함된다. 예를 들어 (1, 1)부터 (2, 2)까지 덮으면 (1, 1), (1, 2), (2, 1), (2, 2)의 총 4칸을 덮는다.

100×100 모자이크에서 보이지 않는 칸의 개수를 구하시오.

입력

첫째 줄에 정수 N과 M이 주어진다. N과 M은 각각 0 이상 50 이하이다.

다음 N개의 줄에는 종이 한 장이 덮는 영역의 좌표가 주어진다. 각 줄은 왼쪽 아래 모서리의 x, y 좌표와 오른쪽 위 모서리의 x, y 좌표 순서로 이루어진다. 모든 좌표는 100 이하의 자연수이다.

출력

첫째 줄에 보이지 않는 칸의 개수를 출력한다.

예제1

  1. 예제 1

    입력
    3 1
21 21 80 80
41 41 60 60
71 71 90 90
    예상 출력
    500