Одной из популярных традиций встречи нового года является запуск в небо фейерверков. Обычно фейерверк взлетает вертикально вверх в течение некоторого времени, после чего взрывается и разделяется на несколько частей, летящих в разных направлениях. Иногда эти части через некоторое время снова взрываются, также разделяясь на несколько частей и так далее.

Лимак живёт на бесконечном клетчатом поле и у него есть один фейерверк. Поведение этого фейерверка после запуска описывается рекурсией глубины n и продолжительностью каждого из уровней рекурсии t₁, t₂, ..., t_n. Как только Лимак запустит фейерверк в какой-нибудь клетке поля, тот начнёт двигаться вверх. После прохождения t₁ клеток (включая стартовую) он взрывается и разделяется на две части, каждая из которых двигается в направлении, изменённом на 45 градусов (для лучшего понимания посмотрите картинки ниже). Таким образом, одна часть будет двигаться в направлении вверх и влево, а другая в направлении вверх и вправо. Каждая из этих частей пройдёт t₂ клеток, после чего также разделится на две части, каждая из которых также изменит траекторию на 45 градусов. Процесс будет продолжаться до n-го уровня рекурсии, после чего все 2^n - 1 частей взорвутся и исчезнут не создавая новых частей.

После нескольких уровней рекурсивного разделения частей фейерверка может так оказаться, что две или более частей находятся в одной и той же клетке в один и тот же момент времени — такая ситуация разрешена и эти части не сталкиваются.

Перед тем как запустить данный фейерверк Лимак хочет убедиться в безопасности этого запуска. Сможете ли вы посчитать количество клеток, которые хотя бы один раз будут посещены какой-либо частью фейерверка?