IOI 2016 Day 2- Aliens > 문제은행 : 정보올림피아드&알고리즘




3681 : Aliens

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
2 회   
시도횟수
8 회   

문제

인공위성이 어떤 외계 행성의 궤도를 돌다가 외계 문명을 발견했다. 그 행성의 어떤 정사각형 영역의 저해상도 사진을 확보했다. 사진에는 지능이 있는 생명체의 흔적이 많이 나타난다. 전문가들이 사진에서 n개의 흥미로운 위치를 찾아내었다. 흥미로운 위치들은 0부터 n-1까지 번호가 붙어 있다. 흥미로운 n개의 위치를 모두 포함하는 고해상도 사진을 찍으려고 한다.

 

 인공위성은 저해상도 사진을 m*m격자로 나누었다. 이렇게 나누었을 때, 정사각형인 하나의 칸을 격자칸이라고 부른다. 격자의 행과 열들은 0부터 m-1까지 번호가 붙어 있다 (위에서 아래로, 왼쪽 에서 오른쪽으로). 우리는 s번째 행, t번째 열에 있는 격자칸을 (s, t)로 표시한다. 흥미로운 위치 i번은 격자칸 (ri, ci)에 포함된다. 하나의 격자칸은 여러 개의 흥미로운 위치를 포함할 수 있다.

 

 인공위성은 행성의 안정적인 궤도를 돌고 있는데, 그 궤도는 격자칸의 중심 대각선 위를 지난다. 중심 대각선이라는 것은 격자의 왼쪽 위 구석과 오른쪽 아래 구석을 잇는 선분을 말한다. 인공위성은 다음 조건을 만족하는 임의의 영역에 대해서 고해상도 사진을 찍을 수 있다.

 

  • 영역의 모양이 정사각형이다.
  • 대각 꼭지점 한 쌍이 모두 중심 대각선 위에 있다.
  • 각각의 격자칸은 영역에 완전히 포함되거나 전혀 포함되지 않아야 한다.

 

인공위성은 최대 k개의 고해상도 사진을 찍을 수 있다.

 

인공위성이 사진을 모두 찍고 나면, 인공위성은 사진에 포함된 모든 (흥미로운 위치가 있는지에 무관하게) 격자칸들에 대한 고해상도 사진을 기지로 전송할 것이다. 사진에 포함된 한 격자칸의 데이터는 단 한 번만 전송된다. 즉, 한 격자칸이 여러번 사진에 찍혔더라도 단 한 번만 전송된다는 것이다.

 

따라서, 다음의 조건을 만족하도록 최대 개의 정사각형 영역을 골라야 한다.

 

  • 흥미로운 위치를 포함하는 격자칸은 적어도 하나의 사진에 포함된다.
  • 적어도 한 번 이상 사진에 찍힌 격자칸의 개수가 최소라야 한다.

 

당신이 할 일은 위의 조건을 만족하는 격자칸의 최소 개수를 찾는 것이다.​ 


입력형식

첫 번째 줄에 n, m, k가 주어진다. (1 ≤ k ≤ n ≤ 100 000, 1 ≤ m ≤ 1 000 000)

두 번째 줄부터 n개의 줄에 흥미로운 위치에 대한 정보 ri, ci가 주어진다. (0 ≤ ri, ci < m)

 


출력형식

격자칸의 최소 개수를 출력한다. 


입력 예

5 7 2
0 3
4 4
4 6
4 5
4 6

출력 예

25

입력 예

2 6 2
1 4
4 1

출력 예

16

Hint!

1번 예제 

그림은 아래와 같다. 첫 번째 그림은 입력 예제를 의미한다. 두 번째 그림처럼 촬영할 수 있지만 이 때의 격자 개수는 41으로, 세 번째 그림처럼 25칸을 촬영하는 것이 더 이득이다.

 
 

 

2번 예제 

그림은 아래와 같다.​ 

 

 

 




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP