카드 하우스

시간 제한2초메모리 제한512 MB

요약

하한 h0가 주어질 때, 전체 카드 수 h(3h+1)/2가 4로 나누어떨어지는 가장 작은 높이 h >= h0를 구한다.

난이도: 보통10점 중 6점
유형: 수학, 정수론, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

수잔은 쓰러지면 나라 전체가 카드에 파묻힐 만큼 거대한 카드 하우스를 세우려고 한다.

카드 하우스는 삼각형 모양이다. 위 사진은 높이가 6인 카드 하우스이다.

높이가 $h$ 인 카드 하우스는 층 $h$ 개로 이루어진다. 위에서 $i$ 번째 층은 서로 기대어 세운 카드 쌍 $i$ 개로 이루어지므로 카드 $2i$ 장을 쓴다. $i$ 번째 층과 $i+1$ 번째 층 사이에는 눕힌 카드 $i$ 장이 들어간다. 따라서 높이가 $h$ 인 카드 하우스에 들어가는 카드는 모두

$\frac{h(3h+1)}{2}$

장이다.

위 그림은 높이가 5인 카드 하우스의 구조이고, 카드 40장을 쓴다.

보기 좋으려면 클로버, 다이아몬드, 하트, 스페이드 네 무늬를 똑같은 장수만큼 써야 한다. 높이에 따라 이렇게 세울 수 있기도 하고 없기도 하다. 높이의 하한 $h_0$ 이 주어질 때, 이런 카드 하우스를 세울 수 있는 가장 작은 높이 $h \ge h_0$ 을 구하라.

입력

첫째 줄에 카드 하우스 높이의 하한을 나타내는 정수 $h_0$ 이 주어진다. ( $1 \le h_0 \le 10^{1000}$ )

출력

네 무늬를 똑같은 장수만큼 써서 세울 수 있는 가장 작은 높이 $h \ge h_0$ 을 출력한다.

예제2

예제 1
입력
```
2
```
예상 출력
```
5
```
예제 2
입력
```
42
```
예상 출력
```
45
```