cho.sh

Going Home

Compute the minimum time to reach the origin from (X,Y) by combining unit-speed walking with fixed-length D jumps costing T seconds each.

Medium5MathGeometryBrute forceNo attempts yetTime limit2sMemory limit128 MB

Problem

Eunjin is currently at coordinate (X, Y), and her home is at the origin (0, 0). She wants to get home as quickly as possible.

There are two ways to move.

  • Walk: move distance 1 in 1 second.
  • Jump: spend T seconds to move exactly distance D in a straight line.

Each jump is straight, and a single jump must have length exactly D. Walking and jumping may be used in any order and any combination. Find the minimum time needed to reach home.

Input

The first line contains four integers X Y D T, separated by spaces.

Output

Print the minimum time needed to reach home. An absolute or relative error of at most 10^-9 is accepted.

Constraints

  • 1 <= X, Y <= 1000
  • 1 <= D, T <= 10000