现在要从上面一行的某一点到最下面的一行某一点，每次只可以到达左下角的点和右下角的点。
求：从上面一行的某一点到最下面的一行某一点的点权之和的最大值是多少。
5609: 蜂窝图
Time Limit: 1.000 Sec Memory Limit: 128 MBSubmit: 14 Solved: 7
[Submit] [Status] [Web Board] [Creator:]
Description
如下图，是一个边长为 3 的蜂窝图，每个点有点权：
现在要从上面一行的某一点到最下面的一行某一点，每次只可以到达左下角的点和右下角的点。
求：从上面一行的某一点到最下面的一行某一点的点权之和的最大值是多少。
现在要从上面一行的某一点到最下面的一行某一点，每次只可以到达左下角的点和右下角的点。
求：从上面一行的某一点到最下面的一行某一点的点权之和的最大值是多少。
Input
第一行一个整数 n 代表蜂窝图的边长。
接下来 2n−1 行每行若干个整数代表一个蜂窝图。
接下来 2n−1 行每行若干个整数代表一个蜂窝图。
Output
一行一个整数代表答案。
Sample Input
3
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4Sample Output
19