저수 칸의 물 나누기

가로와 세로가 각각 N칸인 격자 모양으로 물칸이 붙어 있는 저수 시설이 있다. 각 물칸에는 지금 담겨 있는 물의 양이 자연수로 적혀 있다. 가로나 세로로 맞닿은 두 물칸 사이에는 칸막이가 있으며, 칸막이를 열면 두 칸의 물이 서로 섞인다.

관리인은 다음의 작업을 한 차례씩 되풀이한다.

1) 가로나 세로로 맞닿은 두 물칸을 모두 살펴, 담긴 물의 양의 차이가 L 이상 R 이하인 자리의 칸막이를 연다.

2) 열린 칸막이를 따라 서로 이어진 물칸들을 하나의 묶음으로 본다. 어느 칸막이도 열리지 않아 혼자 남은 물칸도 하나의 묶음이다.

3) 묶음마다 그 묶음에 속한 물칸의 물을 모두 합친 뒤 묶음에 속한 물칸의 수로 나눠, 각 물칸에 그 값만큼 다시 담는다. 나누어 떨어지지 않으면 소수점 아래는 버린다.

4) 칸막이를 모두 닫는다.

1번에서 물의 양을 견주는 기준은 그 차례가 시작될 때의 양이다. 한 차례 안에서 먼저 섞인 물의 양이 다른 칸막이를 여는 판단에 끼어들지는 않는다. 물칸이 둘 이상 들어 있는 묶음이 하나도 없으면 더 이상 물이 옮겨 가지 않으므로 작업을 멈춘다.

결과적으로 처음의 물의 양이 주어졌을 때, 물이 옮겨 간 차례가 모두 몇 번인지 구하는 프로그램을 작성하여라.

예를 들어 N=2이고 L=20, R=50이며 처음의 물의 양이 다음의 표와 같다고 해보자.

첫 차례에는 44와 78의 차이가 34, 44와 12의 차이가 32라서 왼쪽 위 칸을 둘러싼 두 자리의 칸막이가 열린다. 12와 23의 차이는 11이라 L=20에 미치지 못하고, 78과 23의 차이는 55라서 R=50을 넘으므로 그 두 자리는 열리지 않는다. 열린 칸막이로 이어진 44, 78, 12가 한 묶음이 되어 합 134를 3으로 나눈 44씩을 담고, 23은 혼자 남는다.

두 번째 차례에는 23이 담긴 칸이 위쪽의 44와 차이 21, 왼쪽의 44와 차이 21이어서 양쪽 칸막이가 모두 열린다. 나머지 자리는 차이가 0이라 열리지 않는다. 열린 칸막이로 이어진 세 칸의 합 111을 3으로 나눈 37씩을 담고, 왼쪽 위의 44는 혼자 남는다.

세 번째 차례에는 맞닿은 두 칸의 차이가 7이거나 0뿐이어서 L=20에 미치지 못하고, 칸막이가 하나도 열리지 않는다. 따라서 물이 옮겨 간 차례는 두 번이고 이 경우 정답은 2이다.

입출력 예시

예시 1

입력

2 20 50
44 78
12 23

출력

2

예시 2

입력

2 20 50
50 30
20 40

출력

1

예시 3

입력

1 1 1
2

출력

0