eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Пінбол у трикутнику Паскаля

Пінбол у трикутнику Паскаля

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Пінбол у тикутнике Паскаля - гра для однієї людини з гарними арифметичними здібностями. Поле для гри виглядає наступним чином:

У кожном ряду ліворуч і праворуч стоять одиниці, а довільне внутріщнє число отримується як сума двох чисел, які стоять над ним. На початку гри фішка ставиться на верхню одиницю. За хід гравець пересуває фішку на один рядочок вниз і або на півстовбця ліворуч, або на півстовбця праворуч. Наприклад, з четвірки гравець може сходити або на п'ятірку, або на десятку. Зробивши цей хід, гравець отримує кількість очок, рівну сумі цифр у тому числі, на яке він сходив. Для зручності будемо вважати, що за початкове положення фішки (за саму верхню одиницю) гравець також отримує безкоштовне перше очко.

Задача гравця - дійти фішкою до n-го рядка і заробити при цьому максимальну кількість очок. Точніше, це задача для Вашої програми.

Вхідні дані

У вхідному файлі міститься ціле невід'ємне число n - номер рядка, до якого потрібно дістатись (n 30).

Вихідні дані

У вихідний файл виведіть максимальну кількість очок, які можна заробити у цій грі.

Приклад

Вхідні дані #1
2  
Вихідні дані #1
4
Джерело Blitz Contest by SPbETU & Michael Dvorkin, Petrozavodsk Winter Training Session, January 31, 2006