TopCoder

Thumb img 0133
WTF!
我好廢啦晡賴補

User's AC Ratio

100.0% (23/23)

Submission's AC Ratio

82.4% (61/74)

Tags

Description

這是一顆石頭

那有很多顆石頭的時候會發生什麼事呢?
當然就是把它們撿起來啦
李胖有一次在建中(可能是社辦)遊蕩的時候發現地上有一堆石頭,遠遠看好像排成了一個等腰三角形
李胖見獵心喜,想要拿完全部,可是卻發現他每次只能拿左下或右下的那堆石頭
他腦筋動得很快(不愧是總召),馬上想到了要怎麼從現在這裡(等腰三角形頂點)開始拿,拿到社辦門口(等腰三角形底邊),能拿到最多石頭
李胖想到了,可是李胖不說,你也想複製他的走法,該怎麼辦呢?

Input Format

第一行輸入正整數$N, N\le 100$,代表三角形的高
之後$N$行每行代表從頂點到底邊,每堆石頭的個數

Output Format

輸出如果你照著李胖的走法,能夠拿到多少顆石頭

Sample Input

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Sample Output

30

Hints

給定三邊長$a,b,c$的三角形面積公式為$\sqrt{s(s-a)(s-b)(s-c)}$,其中$s=\frac{a+b+c}{2}$

Problem Source

Adapted From IOI 1994
Set By waynetu

Subtasks

For Testdata: 0 ~ 0, Score: 25
For Testdata: 1 ~ 1, Score: 25
For Testdata: 2 ~ 2, Score: 25
For Testdata: 3 ~ 3, Score: 25
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536