헛간 칠하기 (실버)

면접 대비

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

요약

좌표가 0부터 1000까지인 N개의 축에 평행한 직사각형이 주어질 때, 정확히 K개의 직사각형에 덮이는 영역의 넓이를 구한다.

난이도: 보통10점 중 6점
유형: 누적 합, 배열, 구현, 행렬
정답자: 아직 제출이 없습니다

문제

Farmer John은 멀티태스킹을 잘 못한다. 자주 딴 데로 새서 긴 작업을 끝내기 어렵다. 지금 그는 헛간의 한 면을 칠하려 하는데, 작은 직사각형 영역을 칠하다가 소를 돌보느라 자꾸 딴 일을 하러 가서 어떤 부분은 다른 부분보다 더 많은 횟수로 칠해져 있다.

헛간의 한 면을 2D $x$ - $y$ 평면으로 나타내자. Farmer John은 이 평면 위에 변이 좌표축에 평행한 $N$ 개의 직사각형을 칠한다. 각 직사각형은 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 좌표로 주어진다.

Farmer John은 앞으로 당분간 다시 칠할 필요가 없도록 헛간에 여러 번 칠하고 싶다. 하지만 너무 많이 칠해서 시간을 낭비하고 싶지는 않다. $K$ 번 칠하는 것이 최적의 횟수라고 한다. 그가 모든 직사각형을 칠한 뒤, 정확히 $K$ 번 칠해진 헛간의 넓이를 구하자.

입력

첫째 줄에 $N$ 과 $K$ 가 주어진다 ( $1 \leq K \leq N \leq 10^5$ ). 이어지는 $N$ 개의 줄에는 각각 네 정수 $x\_1, y\_1, x\_2, y\_2$ 가 주어지며, 이는 칠하는 직사각형 영역의 왼쪽 아래 꼭짓점 $(x\_1, y\_1)$ 과 오른쪽 위 꼭짓점 $(x\_2, y\_2)$ 를 나타낸다. 모든 $x$ 와 $y$ 값은 $0 \ldots 1000$ 범위에 있고, 모든 직사각형의 넓이는 양수이다.

출력

정확히 $K$ 번 칠해진 헛간의 넓이를 출력한다.

예제1

예제 1
입력
```
3 2
1 1 5 5
4 4 7 6
3 3 8 7
```
예상 출력
```
8
```