시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 933 400 337 44.695%

문제

아즈텍의 황제 쿠이틀라우악은 자신의 명예를 위해 피라미드를 만드려고 한다.

아즈텍 피라미드는 돌 블럭을 이용해서 만든다. 블럭은 1×1×1 크기의 정육면체이다. 쿠이틀라우악은 피라미드의 설립식 때, 블럭 하나를 직접 땅에 놓았다. 그 다음 블럭부터는 인부들이 설치하며, 이전에 놓여진 블럭과 적어도 한 면 전체를 공유해야 한다.

왼쪽 두 개는 가능한 블럭의 배치, 오른쪽 세 개는 불가능한 배치이다.

블럭은 땅의 바로 위에 있거나, 블럭의 아래에 있는 블럭의 모든 면이 땅이나 다른 블럭과 접할 때, 안정적이라고 한다. 피라미드의 모든 블럭은 안정적이어야 한다.

아래 그림은 회색 블럭을 놓았을 때이며, 그 블럭이 안정적인 경우는 왼쪽 세 개, 아닌 경우는 오른쪽 두 개이다.

사용할 수 있는 블럭의 개수가 주어졌을 때, 그 블럭으로 만들 수 있는 가장 높은 안정적인 피라미드의 높이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사용할 수 있는 블럭의 수 n이 주어진다. (1 ≤ n ≤ 109)

출력

첫째 줄에 블럭 n개로 만들 수 있는 가장 높은 안정적인 피라미드의 높이를 출력한다.

예제 입력 1

6

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6Ijc3NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWM5ODhcdWQxNGQgXHVkNTNjXHViNzdjXHViYmY4XHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NDRcdWM5ODhcdWQxNGRcdWM3NTggXHVkNjY5XHVjODFjIFx1Y2ZlMFx1Yzc3NFx1ZDJjMFx1Yjc3Y1x1YzZiMFx1YzU0NVx1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NTggXHViYTg1XHVjNjA4XHViOTdjIFx1YzcwNFx1ZDU3NCBcdWQ1M2NcdWI3N2NcdWJiZjhcdWI0ZGNcdWI5N2MgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHVjOTg4XHVkMTRkIFx1ZDUzY1x1Yjc3Y1x1YmJmOFx1YjRkY1x1YjI5NCBcdWIzY2MgXHViZTE0XHViN2VkXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YmUxNFx1YjdlZFx1Yzc0MCAxJnRpbWVzOzEmdGltZXM7MSBcdWQwNmNcdWFlMzBcdWM3NTggXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHVjNzc0XHViMmU0LiBcdWNmZTBcdWM3NzRcdWQyYzBcdWI3N2NcdWM2YjBcdWM1NDVcdWM3NDAgXHVkNTNjXHViNzdjXHViYmY4XHViNGRjXHVjNzU4IFx1YzEyNFx1YjliZFx1YzJkZCBcdWI1NGMsIFx1YmUxNFx1YjdlZCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjOWMxXHVjODExIFx1YjU0NVx1YzVkMCBcdWIxOTNcdWM1NThcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHViZTE0XHViN2VkXHViZDgwXHVkMTMwXHViMjk0IFx1Yzc3OFx1YmQ4MFx1YjRlNFx1Yzc3NCBcdWMxMjRcdWNlNThcdWQ1NThcdWJhNzAsIFx1Yzc3NFx1YzgwNFx1YzVkMCBcdWIxOTNcdWM1ZWNcdWM5YzQgXHViZTE0XHViN2VkXHVhY2ZjIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHViYTc0IFx1YzgwNFx1Y2NiNFx1Yjk3YyZuYnNwO1x1YWNmNVx1YzcyMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzY3Y1x1Y2FiZCBcdWI0NTAgXHVhYzFjXHViMjk0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJlMTRcdWI3ZWRcdWM3NTggXHViYzMwXHVjZTU4LCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTM4IFx1YWMxY1x1YjI5NCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYzMwXHVjZTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3B5cmExLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojc2cHg7IHdpZHRoOjUxM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmUxNFx1YjdlZFx1Yzc0MCBcdWI1NDVcdWM3NTggXHViYzE0XHViODVjIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWFjNzBcdWIwOTgsIFx1YmUxNFx1YjdlZFx1Yzc1OCBcdWM1NDRcdWI3OThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmUxNFx1YjdlZFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHViYTc0XHVjNzc0IFx1YjU0NVx1Yzc3NFx1YjA5OCBcdWIyZTRcdWI5NzggXHViZTE0XHViN2VkXHVhY2ZjIFx1YzgxMVx1ZDU2MCBcdWI1NGMsIFx1YzU0OFx1YzgxNVx1YzgwMVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDUzY1x1Yjc3Y1x1YmJmOFx1YjRkY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHViZTE0XHViN2VkXHVjNzQwIFx1YzU0OFx1YzgxNVx1YzgwMVx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVkNjhjXHVjMGM5IFx1YmUxNFx1YjdlZFx1Yzc0NCBcdWIxOTNcdWM1NThcdWM3NDQgXHViNTRjXHVjNzc0XHViYTcwLCBcdWFkZjggXHViZTE0XHViN2VkXHVjNzc0IFx1YzU0OFx1YzgxNVx1YzgwMVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNjdjXHVjYWJkIFx1YzEzOCBcdWFjMWMsIFx1YzU0NFx1YjJjYyBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjQ1MCBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcHlyYTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6OTRweDsgd2lkdGg6NjM5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViZTE0XHViN2VkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHViZTE0XHViN2VkXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc4IFx1ZDUzY1x1Yjc3Y1x1YmJmOFx1YjRkY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmUxNFx1YjdlZFx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmUxNFx1YjdlZCBuXHVhYzFjXHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHVjNTQ4XHVjODE1XHVjODAxXHVjNzc4IFx1ZDUzY1x1Yjc3Y1x1YmJmOFx1YjRkY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc3NzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBenRlYyBQeXJhbWlkIiwiZGVzY3JpcHRpb24iOiI8cD5BenRlYyBlbXBlcm9yIEN1aXRsJmFhY3V0ZTtodWFjIGlzIGdvaW5nIHRvIGJ1aWxkIGEgcHlyYW1pZCBpbiBoaXMgaG9ub3IuIFRoaXMgcHlyYW1pZCBzaG91bGQgYmUgdGFsbGVyIHRoYW4gcHJldmlvdXMgb25lcy48XC9wPlxyXG5cclxuPHA+VGhlIEF6dGVjIHB5cmFtaWQgaXMgYnVpbGQgb3V0IG9mIHN0b25lIGJsb2Nrcy4gRWFjaCBibG9jayBpcyAxJnRpbWVzOzEmdGltZXM7MS1odW5hYiBjdWJlLiBDdWl0bCZhYWN1dGU7aHVhYyBwbGFjZXMgXHVmYjAxcnN0IGJsb2NrIG9uIHRoZSBncm91bmQgZHVyaW5nIHRoZSBmb3VuZGF0aW9uIGNlcmVtb255LiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgYmxvY2tzIG11c3Qgc2hhcmUgYSBmYWNlIHdpdGggYXQgbGVhc3Qgb25lIG9mIHRoZSBwcmV2aW91cyBibG9ja3MuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcHlyYTMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTA5cHg7IHdpZHRoOjUyNHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBibG9jayBpcyBzdGFibGUgaWYgaXQgc3RhbmRzIG9uIHRoZSBncm91bmQsIG9yIGl0IHN0YW5kcyBvbiBhbm90aGVyIGJsb2NrLCB0aGF0IGhhcyBhIGJsb2NrIG9yIHRoZSBncm91bmQgbmV4dCB0byBlYWNoIGZhY2UuIFRvIHN0YW5kIHRoZSB0ZXN0IG9mIHRpbWUgdGhlIHB5cmFtaWQgbXVzdCBiZSBzdGFibGUgaS5lLiBlYWNoIGJsb2NrIG9mIGl0IG11c3QgYmUgc3RhYmxlLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3B5cmE0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyN3B4OyB3aWR0aDo2NjdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5DdWl0bCZhYWN1dGU7aHVhYyBhc2tzIHlvdSB0byBkZXRlcm1pbmUgdGhlIGhlaWdodCBvZiB0aGUgdGFsbGVzdCBzdGFibGUgcHlyYW1pZCB0aGF0IGNhbiBiZSBidWlsdCBvdXQgb2YgYXZhaWxhYmxlIGJsb2Nrcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgbnVtYmVyIG4gJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGF2YWlsYWJsZSBibG9ja3MsIGluY2x1ZGluZyB0aGUgXHVmYjAxcnN0IG9uZSAoMSAmbGU7IG4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgaGVpZ2h0IG9mIHRoZSB0YWxsZXN0IHN0YWJsZSBweXJhbWlkIHRoYXQgbWF5IGJlIGJ1aWx0IG91dCBvZiBuIGJsb2Nrcy4gVGhlIGhlaWdodCBtdXN0IGJlIG91dHB1dCBpbiBodW5hYnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d