Garage

Time limit2sMemory limit256 MB

Summary

Place the fewest axis-aligned w by h garages inside a W by H lot so no additional garage fits without moving them.

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

Problem

Your company has just won a public contract for building a garage complex. Almost all formalities are done, and the contract payment is already in your account.

So now it is the right time to read the contract. There is a sandlot in the form of a $W \times H$ rectangle, and you have to place some garages on it. A garage is a $w \times h$ rectangle, and its edges must be parallel to the corresponding edges of the sandlot. You may not rotate a garage, not even by $90^\circ$ . The coordinates of a garage do not have to be integers.

Money must be saved, so you decided to place as few garages as possible. The contract states the opposite requirement: place the maximum possible number of garages.

Here is how that requirement is checked. The plan is accepted if it is impossible to add a new garage without moving the garages already placed. The new garage must also have its edges parallel to the corresponding edges of the sandlot.

Time is money. Find the minimal number of garages you must order, so that you can place all of them on the sandlot and no extra garage fits.

Input

The only line contains four integers $W$ , $H$ , $w$ , $h$ : the width and the height of the sandlot and the width and the height of a garage, in meters. You may assume that $1 \le w \le W \le 30000$ and $1 \le h \le H \le 30000$ .

Output

Print the optimal number of garages.

Note

On an $11 \times 4$ sandlot with a $3 \times 2$ garage, a garage rotated to $2 \times 3$ would still fit, but the contract forbids rotation, so that placement does not count.

Examples3

Example 1
Input
```
11 4 3 2
```
Expected output
```
2
```
Example 2
Input
```
10 8 3 4
```
Expected output
```
2
```
Example 3
Input
```
15 7 4 2
```
Expected output
```
4
```