Competition Hall

Interview

Time limit1sMemory limit1024 MB

Summary

Given N participants on an axis-aligned unit grid with walls at least 1 away, find the minimum area of the hall.

Level: Medium4 of 10
Topics: Math, Brute force
Solved: No attempts yet

Problem

When organizing a contest for PO (Pragmatiska Ortogonalitetsföreningen), participants should sit in a structured layout without sitting too close to each other. This keeps them from disturbing one another and makes cheating harder. The organizers want participants to sit in a regular grid where the distance to the nearest neighbor is at least $1$ (see the figure below). The distance from any participant to a wall must also be at least $1$ . The contest hall is a rectangle whose sides are parallel to the grid.

Given the number of participants $N$ , find the minimum possible area of the contest hall when participants are placed optimally.

Input

A single line with one integer $N$ , the number of participants.

Output

Print one integer on a single line: the minimum possible area of the contest hall.

Constraints

$1 \le N \le 10^9$

Hint

See Figure 1 for an explanation of the input example. The black arrows show the required distance of $1$ between participants and walls.

An illustration of an optimal layout for Sample Input 1.

Examples3

Example 1
Input
```
3
```
Expected output
```
8
```
Example 2
Input
```
7
```
Expected output
```
15
```
Example 3
Input
```
13
```
Expected output
```
24
```