Bakfiets
Tim often needs to transport Fresh Yummy Pomegranate Cocktails in his bakfiets for events of his student association. For this, he has put a rectangular grid of \(a \times b\) in his bakfiets so each bottle fits neatly in a grid cell. The cocktails can be bought in rectangular grid packaging of \(w \times h\), strapped together with some plastic tape. However, these are not necessarily the same dimensions as the grid in his bakfiets. Since Tim was smart enough to make sure that his grid could fit all the bottles, he can remove some of them from the plastic packaging, and put them separately in his bakfiets. What is the minimum number of bottles he needs to remove from the packaging to fit everything in his bakfiets?
As an example, consider the first sample case, visualized in Figure B.1. Tim will need to remove three bottles from the plastic packaging and place these in the remaining space in the bakfiets, in order to make everything fit.
Figure B.1: Visualization of the first sample case. The pink circles represent the bottles in plastic packaging with dimensions \(w \times h = 3 \times 3\) and the black squares represent the bakfiets with dimensions \(a \times b = 5 \times 2\).
Input
- One line with four integers \(w, h, a,\) and \(b \ (1 \le w, h, a, b \le 10^9, \ w \cdot h \le a \cdot b)\). The dimensions of the plastic packaging are \(w \times h\) bottles, and the dimensions of the bakfiets are \(a \times b\) bottles.
Output
- Output the minimum number of bottles Tim needs to remove from the packaging so that all bottles fit in his bakfiets.
Examples
Sample 1
input
3 3 5 2
output
3
Sample 2
input
1 4 3 2
output
1
Sample 3
input
1000000000 1000 1000000 1000000
output
999000000000
Comments