1359: 体育课（一）

体育课上，老师要锻炼大家的弹跳能力，做了一个小游戏。

老师先简单介绍了一下游戏规则，讲了一个小例子，五行15个点：

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

上图是一个俯视图，起点在 7 也就是 (1,1) 位置，每行的点一个人只能踩一次，不能不踩。

XX 想拿到最高分，但是他的身体素质不是太好，他只能从 （i，j）跳到 （i+1 ，j) 或 （i+1，j+1)。

老师讲的小例子， XX 的最优路径 7 -> 3 -> 8 -> 7 -> 5， 最后得分为 30。

第一行一个整数 n （0 < n < 50）。

接下来 n 个 俯视图（每个图18行）。

正式的游戏都是 18 行， 一共 1 + 2 + ... + 18 个点。

每个点的分值都是 s。 （0 <= s <= 1000）

输出 XX 他用尽全力耗尽人品能得到的最高分。

1 61 694 185 439 919 869 539 735 363 96 711 583 963 479 121 295 519 603 332 919 547 443 502 272 550 917 896 829 3 728 748 434 317 143 128 451 791 864 394 777 194 814 804 41 658 676 506 493 963 164 153 415 839 255 754 130 908 109 688 347 412 23 207 609 445 483 725 441 290 527 981 949 97 746 89 406 703 536 72 479 553 732 377 660 772 483 967 683 903 926 389 497 95 688 284 368 819 705 730 184 746 138 421 476 986 434 985 318 906 753 390 133 466 667 349 46 129 895 812 961 399 968 233 382 237 363 787 784 185 538 847 920 166 793 546 661 908 231 234 578 828 144 202 184 14 832 437 126 678 450 442 774 860 802 937 267 468 40 166 240 118 214 107 50 774 779 523 352 974 689 532

11949