시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB299524620.536%

문제

성준이는 무슨 문제든 척척 풀어내는 훌륭한 로봇이다. 이를 시샘한 근수는 성준이가 자는 동안 그의 회로판을 망가뜨렸다.

다행히도 성준이는 자가 치유 프로토콜을 가지고 있어서 이를 이용해 자신을 고쳐보려고 한다. 성준이의 회로판은 $N \times N$ 격자판으로 되어있으며 현재 $M$개의 좌표 $(x_i, y_i)$에 오류가 있다. 성준이는 자신의 회로판을 고치기 위해 다음 2가지 종류의 행동을 반복할 수 있다.

  1. 오류가 $K$개 이하인 모든 가로줄에 대해서, 각 가로줄에 있는 오류들을 전부 제거한다. 오류가 $K$개 초과인 가로줄의 상태는 변하지 않는다.
  2. 오류가 $K$개 이하인 모든 세로줄에 대해서, 각 세로줄에 있는 오류들을 전부 제거한다. 오류가 $K$개 초과인 세로줄의 상태는 변하지 않는다.

성준이는 모든 오류를 제거해 자신을 빠르게 치유하여 자신을 망가뜨린 근수에게 복수하고 싶어 한다. 최소한의 행동으로 성준이의 모든 오류를 제거하는 방법을 구해보자.

입력

첫 번째 줄에 회로판의 크기 $N$, 오류의 개수 $M$, 한 줄에서 치유할 수 있는 최대한의 오류 $K$가 공백으로 구분되어 주어진다. ($1 \le N, M, K \le 2\times10^5$)

두 번째 줄부터 $M+1$ 번째 줄까지 오류의 위치 $(x_i, y_i)$가 공백으로 구분되어 주어진다. ($1 \le x_i, y_i \le N$)

오류의 위치는 중복되어 주어지지 않는다.

출력

성준이가 모든 오류를 제거하기 위한 최소한의 행동 수를 출력한다. 만약 어떠한 방법으로도 성준이가 자신의 오류를 전부 제거할 수 없다면 -1을 출력한다.

예제 입력 1

3 4 1
1 1
2 1
2 2
3 2

예제 출력 1

2

예제 입력 1의 초기 상태 회로판이다. 파란색 칸은 오류를 나타낸다.

행동 2를 실행한다. 첫 번째, 두 번째, 세 번째 세로줄의 오류의 개수는 각각 $1, 2, 1$개이다. $K$ 이하의 오류를 가진 첫 번째, 세 번째 세로줄에 있는 모든 오류들을 전부 제거한다.

행동 1을 실행한다. 첫 번째, 두 번째, 세 번째 가로줄의 오류의 개수는 각각 $1, 1, 0$개이다. $K$ 이하의 오류를 가진 첫 번째, 두 번째, 세 번째 가로줄에 있는 모든 오류들을 전부 제거한다.

모든 오류가 제거되었고, 이때 행동한 횟수는 총 $2$회이다.

예제 입력 2

2 4 1
1 1
2 1
1 2
2 2

예제 출력 2

-1

예제 입력 3

1 1 1
1 1

예제 출력 3

1

출처

University > 서강대학교 > K512컵 > 2024 서강대학교 K512컵 G번