Cake cutting

Time limit1sMemory limit1024 MB

Summary

Given an M by N cake cut into unit squares, plus slanted cuts that form squares of area S at slope Q/P, count the resulting pieces.

Level: Hard8 of 10
Topics: Geometry, Number theory, Math
Solved: No attempts yet

Statement

Kolya's grandmother from the cartoon The Mystery of the Third Planet baked a rectangular cake that she called small. Kolya has many friends to share it with, so the cake is actually quite large. Kolya wanted to help her by cutting the cake into unit squares, but he did not know she still planned to cover it with whipped cream.

The grandmother did not notice Kolya's cuts. She covered the cake with cream and cut it again. She is a very old, very wise, and very artistic woman, and she cuts cakes in her own unique way. Her cuts are slanted and form a square pattern among themselves, following these rules:

The area of the squares formed by her cuts is always an integer.
Her first cut goes diagonally up and to the right, starting from the lower left corner of the cake.
The first cut that crosses it goes diagonally down and to the right, and it intersects the first cut at a distance equal to the side length of the square in her pattern.

How many pieces did Kolya and his grandmother cut the cake into?

Input

The only line of input contains five integers. The first is $M$ ( $1 \le M \le 10^9$ ), the length of the cake from left to right, and the second is $N$ ( $1 \le N \le 10^9$ ), the width of the cake from top to bottom. Kolya cuts the cake into $M \times N$ pieces.

The third number is $S$ ( $1 \le S \le 10^9$ ), the area of the squares formed by the grandmother's cuts. This applies only to pieces that are complete squares. Because her cuts are slanted relative to the edges of the cake, some pieces are smaller than $S$ .

The last two numbers are $P$ and $Q$ ( $1 \le P \le 10^3$ , $1 \le Q \le 10^3$ ), which describe the angle of her cuts. Her first cut is made toward the point that is $P$ units to the right and $Q$ units up from the corner. The angle between Kolya's cuts and hers is $\mathrm{atan}(\frac{Q}{P})$ .

In the late 22nd century, when the story takes place, a new quantum law for cake cutting was found: $\frac{S}{P^2+Q^2}$ is always the square of some rational number.

Output

The only line of output contains a single integer: the total number of pieces into which Kolya's cuts and the grandmother's cuts divide the cake.

Examples4

Example 1
Input
```
5 4 5 2 1
```
Expected output
```
36
```
Example 2
Input
```
7 8 8 1 1
```
Expected output
```
84
```
Example 3
Input
```
8 12 52 2 3
```
Expected output
```
122
```
Example 4
Input
```
3 3 5 11 2
```
Expected output
```
21
```