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