Aliens timer 1초 memory 128MB

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

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

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

• 영역의 모양이 정사각형이다.

• 대각 꼭지점 한 쌍이 모두 중심 대각선 위에 있다.

• 각각의 격자칸은 영역에 완전히 포함되거나 전혀 포함되지 않아야 한다.

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

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

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

• 흥미로운 위치를 포함하는 격자칸은 적어도 하나의 사진에 포함된다.

• 적어도 한 번 이상 사진에 찍힌 격자칸의 개수가 최소라야 한다.

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