울타리 만들기

하카(Haka) 시는 교통 체증으로 유명하다. 꽉 막힌 도로 위에서 하염없이 시간을 보내던 시민들 중 많은 이가 문제 출제자가 되었다. 하카의 넓은 도로 중앙 분리대에는 타공 강판으로 만든 울타리가 늘어서 있는데, 이 문제는 그 강판을 만드는 과정을 다룬다.

모든 타공 강판(strip)에는 각 행마다 정확히 두 개의 원형 구멍이 뚫린다. 패턴 규칙은 다음과 같다.

• 모든 구멍은 반지름이 $r$인 원이다.
• 같은 행에 있는 두 구멍은 서로 $2d$만큼 떨어져 있고, 같은 열에서 이웃한 두 구멍도 서로 $2d$만큼 떨어져 있다.
• 모든 구멍에서 가장 가까운 변까지의 거리는 $d$이다.

이 규칙에 따라 강판의 너비(width)는 항상 $4d + 4r$가 된다. 처음 강판의 길이(length)는 $S$이다.

구멍은 위 규칙에 맞게 완전한 원을 놓을 수 있는 곳에만 뚫는다. 한 강판에 구멍을 다 뚫고 나면, 구멍에서 떼어낸 원판 조각들과 강판의 남는 부분(예를 들어 작업이 끝난 영역의 아래쪽)을 함께 녹여 같은 너비 $4d + 4r$의 새 강판으로 다시 만든다. 이 새 강판에도 같은 규칙으로 구멍을 뚫고, 이 과정을 반복한다. 새로 만든 강판이 너무 짧아 두 구멍짜리 행을 하나도 넣을 수 없게 되면 과정을 멈춘다.

전체 과정에서 뚫은 구멍의 총 개수를 $C(d, r, S)$라 하자. 최소 반지름 $r_{min}$, 최대 반지름 $r_{max}$, 최소 간격 $d_{min}$, 최대 간격 $d_{max}$, 길이 $S$가 주어질 때 다음 값을 구하라.

$\sum_{r=r_{min}}^{r_{max}}\sum_{d=d_{min}}^{d_{max}} C(d, r, S)$

여기서 $d$와 $r$는 항상 정수이다. 처음 강판과 이후에 다시 만든 모든 강판은 어디서나 두께가 균일하고 서로 같다고 가정한다. 풀이는 충분히 효율적이어야 한다.

입력은 최대 1000개의 데이터 집합으로 이루어진다. 각 데이터 집합은 다섯 개의 정수 $r_{min}$, $r_{max}$, $d_{min}$, $d_{max}$, $S$가 한 줄에 주어진다. 범위는 $5000 \le r_{min} \le 10000$, $0 \le r_{max} - r_{min} \le 1000$, $1 \le d_{min} \le 21$, $0 \le d_{max} - d_{min} \le 100$, $1000000 \le S \le 2000000000$이며 $r$와 $d$는 모두 정수이다.

입력의 끝은 다섯 개의 0으로 이루어진 줄로 표시되며, 이 줄은 처리하지 않는다.

각 데이터 집합에 대해 다음 정수를 한 줄에 출력한다.

$\sum_{r=r_{min}}^{r_{max}}\sum_{d=d_{min}}^{d_{max}} C(d, r, S)$

답은 부호 있는 64비트 정수에 충분히 들어간다.