POBEDA-2014

Time limit2sMemory limit1024 MB

Summary

Given counts of four fixed orientations of unit right isosceles triangles, find the largest axis-parallel square that can be tiled using them.

Level: Medium7 of 10
Topics: Greedy, Math, Geometry, Binary search
Solved: No attempts yet

Problem

Modern video cards are known to build images using triangles only. The video card POBEDA-2014 keeps up with this trend. It can display only right isosceles triangles in the four orientations shown in the figures below. The card cannot change the orientation of these triangles.



Type 1	Type 2	Type 3	Type 4

The legs of each triangle shown above are one centimeter long. In one clock cycle the video card can display at most $a_i$ triangles of type $i$ .

You must find the maximum possible side length of a square that the video card can display on the monitor in one clock cycle. The sides of the square must be parallel to the edges of the monitor.

Write a program that solves this problem.

Input

The first line of the input file contains four integers separated by spaces: $a_1$ , $a_2$ , $a_3$ , $a_4$ ( $0 \le a_1, a_2, a_3, a_4 \le 10^{18}$ ). The input can exceed the maximum value of a 32-bit data type.

Output

The output file must contain one number: the maximum possible side length of the square.

Notes

The figure below illustrates the first example.

Examples2

Example 1
Input
```
2 2 2 2
```
Expected output
```
2
```
Example 2
Input
```
10 10 0 0
```
Expected output
```
3
```