# Fence Making

Time Limit: 10 Seconds Memory Limit: 65536 KB

The City of Haka is very famous for its traffic jam. This has given birth to many problem-setters (Those who pose questions for programming contests) as in traffic jam some people have nothing meaningful to do other than thinking about new problems. Most wide roads in Haka have fence along the divider. Perforated steel sheets (As shown in the figure on the left) are often used in these fences.

In this problem we will discuss the manufacturing process of one kind of perforated steel strips and ask you to solve a problem related to this building process.

For
this problem the rectangular perforated steel strips have two circular holes in
each row. Circular holes in the same
row are 2d distance apart. Two consecutive circular holes in the same column
are also 2d distance apart. The distance of each circle from its nearest side
is d. The radius of all the circles is r. So automatically the width of the
metal sheet/strip becomes (4d+4r). The length of the initial sheet is S. Such a
sheet with holes in it is shown in the picture on the right. Holes are only
drilled if they can be cut according to rules mentioned above. The circular
steel sheets which are obtained by cutting the holes and part of the sheet that
is unused (Such as portion below the red dotted line in the figure on the
right) are melted to create a new steel sheet/strip of width (4d+4r). Now holes
are cut according to the rules mentioned above. This process is repeated until
the newly created sheet is so small that two holes (In the same row) cannot be created
in it following the above-mentioned restrictions. Suppose C(d, r, S) denote the
total number of holes that are created. Now given the minimum possible value of
r (r_{min}), maximum possible value of r (r_{max}), minimum
possible value of d (d_{min}) and maximum possible value of d (d_{max})
you will have to find the total number of holes created.

In other words you will have to find:

_{
}

It
should be clear to you now that the value of d and r are always integer. Your method
should be quite efficient. You must assume that the initial given strip and the
strips created later on have equal and uniform thickness in all places.

## Input

nput
file contains 1000 sets of inputs. The input for each set is given in a single
line. Each line contains five integers r_{min} (5,000 ≤ r_{min}
≤ 10,000), r_{max }(0 ≤ r_{max} - r_{min}
≤ 1,000) , dmin (1 ≤ d_{min} ≤ 21), dmax (0 ≤ d_{max}
- d_{min} ≤ 100)and S (1,000,000 ≤ S ≤
2,000,000,000). By now it should be clear to you that value of r and d can only
be a round number.

Input is terminated by a line containing five zeroes. This line should not be processed.

## Output

For
each set/line of input produce one line of output. This line contains an
integer, which denotes the value of

_{
}

You can
safely assume that the value of this integer will comfortably fit in a 64-bit
signed integer. Errors not exceeding 10^{-7 }% will be ignored.

## Sample Input

9682 9719 18 29 71757646 5746 5958 19 24 1942485264 0 0 0 0 0

## Sample Output

15404518 1918408970Submit

Source: ACM ICPC Asia Regional 2011 Phuket Site