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

문제

농부 해강이는 $N \times N$ 칸으로 이루어진 나무판에서 버섯 농사를 짓는다. 나무판은 버섯이 자랄 수 있는 칸과 없는 칸으로 이루어져 있다.

해강이는 $M$개의 버섯 포자를 가지고 있다. 버섯 포자는 버섯이 자랄 수 있는 칸에만 심을 수 있다.

각 버섯 포자는 포자가 심어진 칸을 포함해 최대 $K$개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯을 자라게 한다. 이때 연결된 칸은 상하좌우로 적어도 한 변을 공유하는 칸들의 집합이라고 정의한다.

또한 한 칸에 버섯 포자를 여러 개 겹쳐서 심을 수 있으며, 만약 $x$개의 버섯 포자를 겹쳐 심으면 포자가 심어진 칸을 포함해 최대 $x \times K$개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯이 자란다.

<그림 1> $K = 4$일 때 버섯이 자라는 모습이다.

<그림 2> $K = 10$일 때 버섯이 자라는 모습이다.

해강이는 버섯 포자를 심을 때 최소 개수로만 심으려고 한다. 해강이가 농사가 가능할지 판단하고, 농사가 가능하다면 남은 버섯 포자의 개수를 출력하시오.

버섯 포자를 하나라도 사용하고 버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자랐을 때 농사가 가능하다고 정의한다.

입력

첫 번째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에 나무판의 각 칸의 상태가 공백으로 구분되어 주어진다.

버섯이 자랄 수 있는 칸은 0, 버섯이 자랄 수 없는 칸은 1로 주어진다.

출력

만약 버섯 농사가 불가능하면 IMPOSSIBLE을 출력한다.

버섯 농사가 가능하다면, POSSIBLE을 출력하고 다음 줄에 남은 버섯 포자의 개수를 출력한다.

제한

  • $1 \leq N \leq 100$
  • $0 \leq M \leq 1\,000\,000$
  • $1 \leq K \leq 10^8$
  • $N, M, K$는 모두 정수이다.

서브태스크

번호배점제한
110

$K = 1$

290

추가적인 제약 조건이 없다.

예제 입력 1

5 100 1
1 1 1 0 0
1 0 1 0 0
0 0 1 1 1
1 1 0 0 0
0 1 1 0 1

예제 출력 1

POSSIBLE
88

예제 입력 2

5 5 1
1 1 1 0 0
1 0 1 0 0
0 0 1 1 1
1 1 0 0 0
0 1 1 0 1

예제 출력 2

IMPOSSIBLE

예제 입력 3

5 100 3
1 1 1 0 0
1 0 1 0 0
0 0 1 1 1
1 1 0 0 0
0 1 1 0 1

예제 출력 3

POSSIBLE
94

해당 예제는 서브태스크 1에는 주어지지 않음을 유의하시오.

예제 입력 4

5 5 3
1 1 1 0 0
1 0 1 0 0
0 0 1 1 1
1 1 0 0 0
0 1 1 0 1

예제 출력 4

IMPOSSIBLE

해당 예제는 서브태스크 1에는 주어지지 않음을 유의하시오.

채점 및 기타 정보

  • 예제는 채점하지 않는다.