Fence Making#3102

Fence Making

3 seconds

64 megabytes

Hard

The city of Haka is well known for its traffic jams. This has led to the emergence of many problemsetters, as people often come up with new programming problems while waiting in traffic. Most wide roads in Haka have fences along the divider, and these fences commonly use perforated steel sheets (as shown in the figure on the left).

In this problem, we will discuss the manufacturing process of a particular type of perforated steel strip, and you are asked to solve a problem related to this process.

Each rectangular steel strip has two circular holes in every row. Holes in the same row are $2 d$ units apart. Holes in consecutive rows (that is, in the same column) are also $2 d$ units apart. Each hole is at a distance $d$ from the nearest edge. All holes have radius $r$ . Therefore, the width of each metal strip is $(4 d + 4 r)$ (4d + 4r), and the initial length of the strip is $S$ . Such a strip is shown in the right image. Holes are drilled only if they can be cut following these rules. The circular steel sheets obtained from the holes and the unused part of the strip (for example, the part below the red dotted line in the right image) are melted to create a new steel strip of width $(4 d + 4 r)$ (4d + 4r). Then, holes are cut in the new strip according to the same rules. This process repeats until the newly created strip is so small that it is impossible to create two holes in one row, subject to the above restrictions.

Let $C (d, r, S)$ C(d, r, S) denote the total number of holes produced. Given $r_{min}$ r_{min} (the minimum possible value of $r$ ), $r_{ma x}$ r_{max} (the maximum possible value of $r$ ), $d_{min}$ d_{min} (the minimum possible value of $d$ ), $d_{ma x}$ d_{max} (the maximum possible value of $d$ ), and $S$ , you need to find the total number of holes produced.

You may assume all values of $d$ and $r$ are integers. The initial and all subsequent strips have equal and uniform thickness everywhere. Your method should be efficient enough for the constraints.

Input

The input file contains up to $1000$ test cases. Each test case is presented on a single line, containing five integers:

$r_{min}$ r_{min} $(5000 \leq r_{min} \leq 10000)$ (5000 \leq r_{min} \leq 10\,000), $r_{ma x}$ r_{max} $(0 \leq r_{ma x} - r_{min} \leq 1000)$ (0 \leq r_{max} - r_{min} \leq 1\,000), $d_{min}$ d_{min} $(1 \leq d_{min} \leq 21)$ (1 \leq d_{min} \leq 21), $d_{ma x}$ d_{max} $(0 \leq d_{ma x} - d_{min} \leq 100)$ (0 \leq d_{max} - d_{min} \leq 100), $S$ $(1000000 \leq S \leq 2000000000)$ (1\,000\,000 \leq S \leq 2\,000\,000\,000).

The input ends with a line containing five zeros. This line should not be processed.

Output

For each input line, output a single integer which denotes the total number of holes produced, summed for all $d$ and $r$ in the given ranges. The value will fit into a $64$ -bit signed integer. Answers with a relative error not exceeding $1 0^{- 7} %$ 10^{-7}\% will be accepted.

Examples

Example 1