어항 정리

마법사 상어는 그동안 배운 마법으로 어항을 정리하려고 한다. 어항은 한 변의 길이가 1인 정육면체 모양이고, 상어에게는 어항이 $N$개 있다. 처음에 어항은 바닥 위에 일렬로 놓여 있고, 각 어항에는 물고기가 한 마리 이상 들어 있다. <그림 1>은 어항 8개가 바닥 위에 일렬로 놓인 상태이며, 칸에 적힌 값은 그 어항에 들어 있는 물고기의 수이다. 편의상 어항은 정사각형으로 표현했다.

<그림 1>

어항을 한 번 정리하는 과정은 다음과 같다.

먼저 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 그러한 어항이 여러 개라면 물고기의 수가 가장 적은 어항 모두에 한 마리씩 넣는다. 위의 그림 1에서는 물고기의 수가 가장 적은 어항에 물고기가 2마리 있고, 그러한 어항은 2개이다. 따라서 2개의 어항에 물고기를 한 마리씩 넣으면 <그림 2>와 같아진다.

<그림 2>

이제 어항을 쌓는다. 먼저 가장 왼쪽에 있는 어항을 그 오른쪽에 있는 어항의 위에 올려 놓으면 <그림 3>이 된다.

<그림 3>

이제 2개 이상 쌓여 있는 어항을 모두 공중 부양시킨 다음, 전체를 시계 방향으로 90도 회전시킨다. 이후 공중 부양시킨 어항을 바닥에 있는 어항의 위에 올려 놓는다. 바닥의 가장 왼쪽에 있는 어항 위에 공중 부양시킨 어항 중 가장 왼쪽에 있는 어항이 있어야 한다. 이 작업은 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 있을 때까지 반복한다.

먼저 <그림 4>와 같이 어항이 놓인 상태가 변하고, 한 번 더 변하면 <그림 5>가 된다.

<그림 4>

<그림 5>

<그림 5>에서 어항을 한 번 더 공중 부양시키는 것은 불가능하다. <그림 6>과 같이 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 없기 때문이다.

<그림 6>

공중 부양 작업이 모두 끝나면 어항에 있는 물고기의 수를 조절한다.

모든 인접한 두 어항의 물고기 수 차이를 구한다. 이 차이를 5로 나눈 몫을 $d$라고 하자. $d$가 0보다 크면 두 어항 중 물고기가 많은 어항에서 적은 어항으로 물고기 $d$마리를 보낸다. 이 과정은 모든 인접한 칸에서 동시에 일어난다. 이 과정이 끝나면 <그림 7>이 된다.

<그림 7>

이제 어항을 다시 바닥에 일렬로 놓아야 한다. 가장 왼쪽에 있는 어항부터, 각 위치마다 아래에 있는 어항부터 가장 위에 있는 어항까지 순서대로 바닥에 놓는다. <그림 8>은 어항을 다시 바닥에 일렬로 놓은 상태이다.

<그림 8>

다시 공중 부양 작업을 해야 한다. 이번에는 가운데를 중심으로 왼쪽 $N/2$개를 공중 부양시켜 전체를 시계 방향으로 180도 회전시킨 다음, 오른쪽 $N/2$개의 위에 놓는다. 이 작업은 두 번 반복해야 한다. 두 번 반복하면 바닥에 있는 어항의 수는 $N/4$개가 된다. <그림 9>는 이 작업을 한 번 했을 때이고, <그림 10>은 다시 한 번 더 했을 때이다.

<그림 9>

<그림 10>

여기서 다시 위에서 한 물고기 수 조절 작업을 수행하고, 어항을 바닥에 일렬로 놓는 작업을 수행한다. <그림 10>에서 조절 작업을 마친 결과는 <그림 11>이 되고, 여기서 다시 어항을 바닥에 일렬로 놓으면 <그림 12>가 된다.

<그림 11>

<그림 12>

어항의 수 $N$과 각 어항에 들어 있는 물고기의 수가 주어진다. 물고기가 가장 많이 들어 있는 어항과 가장 적게 들어 있는 어항의 물고기 수 차이가 $K$ 이하가 되려면 어항을 몇 번 정리해야 하는지 구하자.

첫째 줄에 $N$과 $K$가 주어진다. 둘째 줄에 가장 왼쪽에 있는 어항부터 오른쪽에 있는 어항까지 각 어항에 들어 있는 물고기의 수가 순서대로 주어진다.

물고기가 가장 많이 들어 있는 어항과 가장 적게 들어 있는 어항의 물고기 수 차이가 $K$ 이하가 되려면 어항을 몇 번 정리해야 하는지 출력한다.

• $4 \le N \le 100$
• $N$은 4의 배수이다.
• $0 \le K \le 10$
• 각 어항에 들어 있는 물고기의 수는 1 이상 10,000 이하이다.