Walking

Interview

Time limit2sMemory limit128 MB

Summary

Compute the minimum time to walk from (0,0) to (X,Y) on a grid where straight moves cost W and diagonal moves cost S.

Level: Easy3 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

Sejun wants to walk home from school. The city is an infinite grid: there is a vertical road at every integer x-coordinate and a horizontal road at every integer y-coordinate. Sejun starts at (0, 0), and his home is at (X, Y).

In one move, he can either move one block horizontally or vertically along the roads, or cross one block diagonally.

Find the minimum time needed for Sejun to get home.

Input

The first line contains four integers X Y W S. X and Y are the coordinates of the home. W is the time needed to move one block along a road, and S is the time needed to cross one block diagonally.

X and Y are integers between 0 and 1,000,000,000 inclusive. W and S are integers between 1 and 10,000 inclusive.

Output

Print the minimum time needed to get home.

Examples7

Example 1
Input
```
4 2 3 10
```
Expected output
```
18
```
Example 2
Input
```
4 2 3 5
```
Expected output
```
16
```
Example 3
Input
```
2 0 12 10
```
Expected output
```
20
```
Example 4
Input
```
25 18 7 11
```
Expected output
```
247
```
Example 5
Input
```
24 16 12 10
```
Expected output
```
240
```
Example 6
Input
```
10000000 50000000 800 901
```
Expected output
```
41010000000
```
Example 7
Input
```
135 122 43 29
```
Expected output
```
3929
```