Fence Making

The city of Haka is famous for its traffic jams. All that idle time in traffic has turned many of its citizens into problem setters. Along the dividers of Haka's wide roads run fences made of perforated steel sheets, and this problem is about how those sheets are made.

Every perforated steel strip has exactly two circular holes in each row. The pattern rules are:

• Every hole is a circle of radius $r$.
• The two holes in the same row are $2d$ apart, and two consecutive holes in the same column are also $2d$ apart.
• The distance from every hole to its nearest side of the strip is $d$.

Because of these rules the width of every strip is exactly $4d + 4r$. The length of the initial sheet is $S$.

A hole is drilled only where a full circle fits under the rules above. Once a sheet has been drilled, the circular pieces taken from the holes, together with the unused part of the sheet (for example the portion below the finished region), are melted down and cast into a new strip of the same width $4d + 4r$. Holes are drilled into that new strip under the same rules, and the process repeats. It stops as soon as the freshly cast strip becomes too short to hold even one row of two holes.

Let $C(d, r, S)$ be the total number of holes drilled during the entire process. Given the minimum radius $r_{min}$, the maximum radius $r_{max}$, the minimum spacing $d_{min}$, the maximum spacing $d_{max}$ and the length $S$, compute

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

Here $d$ and $r$ are always integers. Assume the initial strip and every strip cast afterwards have the same uniform thickness everywhere. Your method must be efficient.

The input contains up to 1000 data sets. Each data set is a single line of five integers $r_{min}$, $r_{max}$, $d_{min}$, $d_{max}$ and $S$, with $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$ and $1000000 \le S \le 2000000000$. All of $r$ and $d$ are integers.

The input ends with a line of five zeros, which must not be processed.

For each data set print a single line containing the integer

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

The answer fits comfortably in a signed 64-bit integer.