Pinball in Pascal's Triangle#4877

Pinball in Pascal's Triangle

1 second
64 megabytes
Very easy

Pinball in Pascal's Triangle is a solo game designed for those with strong arithmetic skills. The playing field is structured as follows:

In each row of Pascal's Triangle, the numbers on the edges are ones, and any number inside is the sum of the two numbers directly above it. The game begins with a token placed on the topmost one. During each move, the player can slide the token one row down, choosing to move either half a column to the left or half a column to the right. For instance, from the number four, the player can move to either five or ten. After each move, the player scores points equal to the sum of the digits of the number they land on. For simplicity, the player starts with one free point for the initial position at the top.

The objective is to navigate the token to the -th row while maximizing the total points scored. Your task is to write a program to achieve this.

Input

The input consists of a single non-negative integer , representing the target row number (n \leq 30).

Output

Output the maximum number of points that can be accumulated in this game.

Examples

Example 1

Loading
Loading