Hide

Problem D
House of Cards

/problems/houseofcards/file/statement/en/img-0001.jpg

Picture by Liftarn on Wikipedia, public domain

Brian and Susan are old friends, and they always dare each other to do reckless things. Recently Brian had the audacity to take the bottom right exit out of their annual maze race, instead of the usual top left one. In order to trump this, Susan needs to think big. She will build a house of cards so big that, should it topple over, the entire country would be buried by cards. It’s going to be huge!

The house will have a triangular shape. The illustration to the right shows a house of height $6$ , and Figure 1 shows a schematic figure of a house of height $5$ .

For aesthetic reasons, the cards used to build the tower should feature each of the four suits (clubs, diamonds, hearts, spades) equally often. Depending on the height of the tower, this may or may not be possible. Given a lower bound $h_{0}$ on the height of the tower, what is the smallest possible height $h \geq h_{0}$ such that it is possible to build the tower?

$\includegraphics[width=0.25\textwidth ]{fig}$

Figure 1: A house of height

5

uses

40

cards.

Input

A single integer $1 \leq h_{0} \leq 10^{1000}$ , the minimum height of the tower.

Output

An integer, the smallest $h \geq h_{0}$ such that it is possible to build a tower of height $h$ .

Sample Input 1	Sample Output 1
2	5

Sample Input 2	Sample Output 2
42	45

Problem DHouse of Cards

Input

Output

Problem D
House of Cards