# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Limits
1s, 512 MB

Sathi is an intelligent girl. She likes to play with mathematical problems. Everyday she makes some new interesting problems by herself and then tries to solve it. But, some problems take too much time in finding out the desired result and she can’t even make herself sure about this result. So, recently she learned about programming and she also learned that every mathematical problem can be solved by computer too accurately and very quickly by building correct programs for it.

Today, she comes up with a new interesting pyramid problem. There are **N** integers (**N** is always an odd number) in the first row and every next row, the numbers decrease exactly by two each time compared to the previous row and the last row has exactly one integer. (see in Fig-1) Then, she draws some combination lines (Fig-1) on it and gets some series of numbers. She keeps a record of all sum of these series and finds out the maximum one.

1st series sum = 24 + 10 + 0 + 10 + 24 = 68

2nd series sum = 12 + 10 + 12 = 34

3rd series sum = 12 = 12

So, among all sums, 68 is the maximum.

After finding this out, Sathi now wants to write a program to check whether her answer is right or not. But, soon she realizes that it is not so easy to write such a program as she is not that much expert yet. So, now your task is to help Sathi by writing such a program in which Sathi can check the maximum sum of any such interesting pyramids she makes.

There will be multiple test cases in each input file where each test case represents a new such pyramid.

First line will contain an odd number **N**, denoting the number of integers of the first row of pyramids. Each pyramid contains exactly **N/2+1** rows where each row contains exactly two less number of integers compared to the previous row and the last row contains exactly one integer. No integer will exceed **10 ^{3}**.

The input file will be terminated when **N = 0** and each input file will contain at most **30** test cases.

For each case, print the maximum sum in a new line by the process that is already defined above.

Input | Output |
---|---|

5 24 12 12 12 24 10 10 10 0 0 | 68 |

75% Solution Ratio

emrul_muEarliest,

dip_BRURFastest, 0.0s

emrul_muLightest, 131 kB

nafiamahjabinShortest, 766B

Login to submit