Задача A. Новогодние игрушки

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Скоро Новый Год! А это значит, что самое время украшать ёлку красивыми, разноцветными и яркими игрушками.

Ёлочка Тимофея имеет свою красоту, равную количеству ветвей с одной стороны ствола и (так уж совпало) длине самой нижней ветви. Каждая следующая верхняя ветка на одну клетку короче предыдущей. Между ветвями, а также под самой нижней и над самой верхней ветвями находится ствол дерева шириной ровно в одну клетку. На рисунке вы видите ёлки красотой от 0 до 5 включительно. Каждая игрушка может располагается на одной из клеток, принадлежащей ёлке.

Тимофей хочет разместить на своей ёлке как можно больше игрушек. При этом, чтобы не портить впечатление, он решил, что игрушки не могут занимать две соседние клетки (но могут касаться углами). Помогите Тимофею узнать наибольшее количество игрушек, которыми ему удастся украсить ёлку красотой n.

Формат входных данных

В единственной строке записано одно неотрицательное целое число n — красота елки.

Формат выходных данных

Выведете одно натуральное число — ответ на задачу.

Ограничения

0 ≤ n ≤ 109

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: n ≤ 105, баллы: 30.

Подзадача 2: нет дополнительных ограничений, баллы: 70.

Пояснение к примеру

В примере дана ёлка красоты 5. Пример украшения — на рисунке.

Примеры тестов

Стандартный вход Стандартный выход
1
5
24

0.092s 0.017s 19