Garage Placement Optimization

Wow! What a lucky day! Your company has won a social contract to build a garage complex on a sandlot. The sandlot is a rectangle of dimensions \(W \times H\). You are to place garages of dimensions \(w \times h\) (with edges parallel to the sandlot’s edges; rotation is not allowed) on the sandlot. The coordinates of the garages may be non‐integer.

Your goal is to order as few garages as possible. However, the contract also requires that the final placement is maximal: it must be impossible to add one more garage (with edges parallel to the sandlot) without moving the other garages.

In other words, you need to find the minimal number of garages that can be placed on the sandlot so that for any valid placement of a new garage (i.e. any bottom‐left coordinate \((x,y)\) with \(0 \le x \le W-w\) and \(0 \le y \le H-h\)), the new garage will overlap with at least one of the existing garages.

Observation and Hint:

Any garage placed at point \((a,b)\) (so that its rectangle occupies \([a, a+w] \times [b, b+h]\)) will overlap any newly placed garage with bottom-left corner \((x,y)\) provided that:

[ x < a+w \quad \text{and} \quad x+w > a, \quad \text{and} \quad y < b+h \quad \text{and} \quad y+h > b. ]

This is equivalent to saying that the new garage’s placement \((x,y)\) lies in the open rectangle \((a-w, a+w) \times (b-h, b+h)\). The problem of saturating the sandlot becomes one of covering the entire set of possible placements, \([0, W-w] \times [0, H-h]\), with such "blocking" rectangles.

It turns out that an optimal strategy is to arrange the garages in a grid where each garage \(G\) placed at \((a,b)\) covers an effective region of size \(2w \times 2h\) in the placement space. More precisely, if we define \(X = W-w\) and \(Y = H-h\), then the minimal number of garages required is

[ \text{answer} = \max\Bigl{1, \Bigl\lceil \frac{X}{2w} \Bigr\rceil\Bigr} \times \max\Bigl{1, \Bigl\lceil \frac{Y}{2h} \Bigr\rceil\Bigr}. ]

This formula ensures that even in the edge cases in which \(W = w\) or \(H = h\) (so that there is only one possible placement in that direction), at least one garage is used.

Your task is to compute this minimal number given \(W, H, w, h\).

inputFormat

The input consists of a single line containing four space-separated integers:

• \(W\) and \(H\): the width and height of the sandlot.
• \(w\) and \(h\): the width and height of a garage.

You can assume that \(1 \le w \le W \le 10^9\) and \(1 \le h \le H \le 10^9\).

outputFormat

Output a single integer: the minimal number of garages required so that the placement is maximal (i.e. no additional garage can be inserted without overlapping an existing one).

sample

15 15 10 10

1