시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB468877026.022%

문제

2차원 좌표 평면에 변이 축에 평행한 직사각형 N개가 있다. 직사각형은 1부터 N까지 번호가 매겨져 있다. i번 직사각형의 왼쪽 아래 꼭짓점의 좌표는 (xi,1, yi,1)이고, 오른쪽 위 꼭짓점의 좌표는 (xi,2, yi,2)이다. N개의 직사각형 중 K개를 칠해 색칠된 영역의 최댓값을 구해보자.

일부 영역은 하나 이상의 직사각형이 있을 수도 있다. 이 경우 그 영역에 있는 직사각형 중 가장 높은 번호를 가진 직사각형만 보이는 것이다. 예제 1을 참고한다.

입력

첫째 줄에 두 정수 N, K가 주어진다. 둘째 줄부터 N개의 줄에 직사각형을 나타내는 네 정수 xi,1, yi,1, xi,2, yi,2가 주어진다.

출력

첫째 줄에 색칠한 면적을 최대로 하려면, 어떤 직사각형을 칠해야 하는지 출력한다. 빈 칸으로 구분하며, 여러 가지일 경우에는 사전순으로 앞서는 것을 출력한다.

제한

  • 1 ≤ K ≤ N ≤ 50
  • -10,000 ≤ xi,1, yi,1, xi,2, yi,2 ≤ 10,000
  • xi,1 < xi,2
  • yi,1 < yi,2

예제 입력 1

3 2
1 1 5 3
3 2 7 4
2 5 9 7

예제 출력 1

2 3

예제 입력 2

7 4
1 1 5 4
2 2 4 3
4 0 6 2
7 1 9 4
1 5 4 7
6 5 9 7
2 5 8 6

예제 출력 2

1 3 4 7

예제 입력 3

4 3
-1 -5 1 1
2 2 5 6
-2 3 1 7
2 -4 6 -1

예제 출력 3

1 2 3

출처