Building Fences

Time limit2sMemory limit128 MB

Summary
Given N fence pieces on an infinite hexagonal grid, compute the maximum number of blocks (fence plus enclosed area) a single connected fence loop using all N pieces can occupy.
Level

Hard8 of 10

Topics
Geometry, Math, Combinatorics, Greedy
Solved
No attempts yet

Problem

There is an infinite RPG world made of hexagonal blocks. A character has N items, each of which can turn one normal block into a fence block. Use all N items so that the fence blocks are connected, and find the maximum possible area of territory.

Blocks enclosed by the fence are counted as territory, and the fence blocks themselves are also counted. The map is infinite.

Input

The first line contains the number of items N.

  • 1 ≤ N ≤ 1,000,000

Output

Print the maximum number of blocks that can be occupied.

Examples1

  1. Example 1

    Input
    6
    Expected output
    7