#include<bits/stdc++.h>//头文件 
using namespace std;
const int N=1e3+10;
int a[N][N],f[N][N][2],n,ans;
//定义变量 

int main(){//主函数 
	cin>>n;//输入 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
			if(i==n){
				f[i][j][0]=a[i][j];
			}
		}
	for(int i=4;i>=1;i--)
		for(int j=1;j>=i;j++){
			if(f[i+1][j][0]>f[i+1][j+1][0]){
				f[i][j][0]=f[i+1][j][0]+a[i][j];
				f[i][j][1]=1;
			}
		}
	
	ans = f[1][1][0];
	cout<<ans<<endl;
	int x=1,y=1;
	while(x<=5){
		cout<<a[x][y]<<" ";
		x++;
		if(f[x][y][1]==1)y++;
	}
	return 0;//结束 
}

#include<bits/stdc++.h>//头文件 
using namespace std; 
const int N=1e3+10;
int a[N][N],f[N][N],n,ans;
//定义变量 

int main(){//主函数 
	cin>>n;//输入 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++){
			cin>>a[i][j];//输入 
		}
	f[1][1]=a[1][1];//边界 
	for(int i=2;i<=n;i++)
		for(int j=1;i<=i;j++)
			f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
	for(int i=1;i<=n;i++){
		ans = max(ans,f[n][i]);//擂台法
	}
	cout<<ans;//输出 
	return 0;//结束 
}

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
const int N = 1e3 + 10; //数组大小
int a[N][N], f[N][N], n, ans; //储存数字塔的数组，数字塔层数，答案
int main() { //主函数
	cin >> n; //输入数字塔大小
	for (int i = 1; i <= n; i++) { //行
		for (int j = 1; j <= i; j++) {
			cin >> a[i][j];
			f[i][j] = -1;
		}//输入
	}
	f[1][1] = a[1][1];//调边界值
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++){
			f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j]; //状态转移方程式
		}
	}
	for (int i = 1; i <= n; i++) {
		ans = max(ans, f[n][i]); //max求最大值
	}
	cout << ans; //输出
	return 0;//结束
}

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
const int N = 1e3 + 10;//建1个变量N大小是1010
int a[N][N], f[N][N], n, ans;//建变量ans,n ans是最终答案 n是层数 数组a是存储数字金字塔
int main() {
	cin>>n;//输入
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
			f[i][j]=-1;//输入
		}
	}
	f[1][1]=a[1][1];//边界
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];//状态转移方程
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,f[n][i]);//求到达最底层的权重和的最大值
	}
	cout<<ans;//输出
	return 0;
}

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
const int N=1e3+10;//数组大小
int a[N][N],f[N][N],n,ans;//储存数字塔的数组，递归数据，数字塔大小，答案
int main(){//主函数
	cin>>n;//输入数字塔大小
	for(int i=1;i<=n;i++){//行
		for(int j=1;j<=i;j++){cin>>a[i][j];f[i][j]=-1;};//输入数字塔，并把f数组设为-1
	}
	f[1][1]=a[1][1];//边界值
	for(int i=1;i<=n;i++){//行数
		for(int j=1;j<=i;j++)f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];//转移方程
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,f[n][i]);//擂台法求最大值
	}
	cout<<ans;//输出答案
	return 0;//结束程序
}

#include<bits/stdc++.h>//头文件 
using namespace std;//命名空间 
const int N = 1e3+10;
int a[N][N],f[N][N],n,ans;//定义变量 

int dp(int x,int y){
	if(f[x][y]!=-1){//判断 
		return f[x][y];//返回 
	}else{
		f[x][y]=may(dp(x-1,y-1),dp(x-1,y))+a[x][y];//转移方程 
		return f[x][y];//返回 
	}
}

int main(){
	cin>>n;//输入 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			f[i][j]=-1;	
		}
	f[1][1]=a[1][1];
	for(int i=1;i<=n;i++){     //求最大值 
		ans = max(ans,dp(n,i));//求最大值 
	}
	cout<<ans;//输出
	return 0;//结束程序 
}

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
const int N = 1e3 + 10;//建1个变量N大小是1010
int a[N][N], f[N][N], n, ans;//建变量ans,n ans是最终答案 n是层数 数组a是存储数字金字塔
int dp(int x, int y) {//建变量x,y
	if (f[x][y] != -1) {//搜索过
		return f[x][y];//跳出递归
	} else {
		f[x][y]=max(dp(x-1,y-1),dp(x-1,y))+a[x][y];//状态转移方程
		return f[x][y];//跳出递归
	}
}
int main() {
	cin>>n;//输入
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
			f[i][j]=-1;//输入
		}
	}
	f[1][1]=a[1][1];//边界
	for(int i=1;i<=n;i++){
		ans=max(ans,dp(n,i));//求到达最底层的权重和的最大值
	}
	cout<<ans;//输出
	return 0;
}

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
int a[1010][1010],f[1010][1010],n,ans;//储存数字塔的数组，递归数据，数字塔大小
int dp(int x,int y){//动态规划
	if(f[x][y]!=-1){//搜索过
		return f[x][y];//跳出递归
	}else{
		f[x][y]=max(dp(x-1,y-1),dp(x-1,y))+a[x][y];//状态转移方程
		return f[x][y];//跳出递归
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
			f[i][j]=-1;
		}
	}//输入
	f[1][1]=a[1][1];//边界
	for(int i=1;i<=n;i++){
		ans=max(ans,dp(n,i));//到达最底层的权重和的最大值
	}
	cout<<ans;//输出
	return 0;
}

#include<bits/stdc++.h>//头文件 
using namespace std; 
const int N=1e3+10;
int a[N][N],f[N][N],n,ans;
//定义变量 

int dp(int x,int y){
	if(f[x][y]!=-1){//判断 
		return f[x][y];//返回
	}else{
		f[x][y]=max(dp(x-1,y-1),dp(x-1,y))+a[x][y];//状态转移方程 
		return f[x][y];//返回 
	}
}

int main(){//主函数 
	cin>>n;//输入 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++){
			cin>>a[i][j];//输入 
			f[i][j]=-1;
		}
	f[1][1]=a[1][1];//边界 
	for(int i=1;i<=n;i++){//擂台法 到达最底层的权重和的最大值 
		ans = max(ans,dp(n,i));//dp 
	}
	cout<<ans;//输出 
	return 0;//结束 
}

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
const int N=1e3+10;//数组大小
int a[N][N],f[N][N],n,ans;//储存数字塔的数组，递归数据，数字塔大小，答案
int dp(int x,int y){//动态规划
	if(f[x][y]!=-1)return f[x][y];//判断是否到达过该元素
	else{//否则
		f[x][y]=max(dp(x-1,y-1),dp(x-1,y))+a[x][y];//状态转移方程
		return f[x][y];//返回转移后的数据
	}
}
int main(){//主函数
	cin>>n;//输入数字塔大小
	for(int i=1;i<=n;i++){//行
		for(int j=1;j<=i;j++){cin>>a[i][j];f[i][j]=-1;};//输入数字塔，并把f数组设为-1
	}
	f[1][1]=a[1][1];//边界值
	for(int i=1;i<=n;i++){//行数
		ans=max(ans,dp(n,i));//擂台法求最大值
	}
	cout<<ans;//输出答案
	return 0;//结束程序
}

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
const int N = 1e4 + 10;//建1个变量N大小是1010
int a[N][N], f[N][N], ans, n; //建变量ans,n ans是最终答案 n是层数 数组a是存储数字金字塔
int Dfs(int x, int y) { //x是横 y是第多少个
	if (f[x][y] == -1) { //判断（x,y） 是否已经求出f[x][y] 
		if (x == n) { //判断是否到底层
			f[x][y] = a[x][y];//返回元素
		} else {
			f[x][y] = max(Dfs(x + 1, y), Dfs(x + 1, y + 1)) + a[x][y];
		}
	}
	return f[x][y];//结束
}
int main() { //主函数
	cin >> n;//输入
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> a[i][j];
			f[i][j] = -1;//输入
		}
	}
	ans = 0;
	Dfs(1, 1);
	cout << f[1][1] << endl;//输出
	return 0;//结束
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int A[N][N],F[N][N],n,ans;
//定义数组A,F变量 n,ans 

int Dfs(int x,int y){
// x代表走到了数字塔的第几层
// y代表走到了数字塔的第几个
	if(F[x][y]==-1){//判断（x,y） 是否已经求出f[x][y] ;
		if(x==n)F[x][y]=A[x][y];
		else{
			F[x][y]=max(Dfs(x+1,y),Dfs(x+1,y+1))+A[x][y];
		}
	}
	return F[x][y];//结束 
}

int main(){
	cin>>n;//输入 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++){
			cin>>A[i][j];//输入 
			F[i][j]=-1;
		}
	ans=0;
	Dfs(1,1);
	cout<<F[1][1]<<endl;//输出 
	return 0;//结束 
}

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
const int N=1e4+10;//数组大小
int a[N][N],f[N][N],n,ans=0;//储存数字塔的数组，递归数据，数字塔大小
int dfs(int x,int y){//数字坐标
	if(f[x][y]==-1){//判断是否到过
		if(x==n)f[x][y]=a[x][y];//如果到底返回元素
		else f[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];//调用dfs求答案
	}
	return f[x][y];//返回数字
}
int main(){//主函数
	cin>>n;//输入数字塔大小
	for(int i=1;i<=n;i++){//行数
		for(int j=1;j<=i;j++){cin>>a[i][j];f[i][j]=-1;}//输入数字塔
	}
	dfs(1,1);//把f[1][1]变成答案
    cout<<f[1][1];//输出答案
	return 0;//结束程序
}

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
const int N=1e4+10;//数组大小
int a[N][N],f[N][N],n,ans=0;//储存数字塔的数组，递归数据，数字塔大小
int dfs(int x,int y){//数字坐标
	if(f[x][y]==-1){//判断是否到过
		if(x==n)f[x][y]=a[x][y];//如果到底返回元素
		else f[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];//返回底下更大的数
	}
	return f[x][y];//返回数字
}
int main(){//主函数
	cin>>n;//输入数字塔大小
	for(int i=1;i<=n;i++){//行数
		for(int j=1;j<=i;j++){cin>>a[i][j];f[i][j]=-1;}//输入数字塔
	}
	dfs(1,1);//把f[1][1]变成答案
    cout<<f[1][1];//输出答案
	return 0;//结束程序
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int A[N][N],F[N][N],n,ans;
//定义数组A,F变量 n,ans 

int Dfs(int x,int y){
// x代表走到了数字塔的第几层
// y代表走到了数字塔的第几个
// Curr代表走到当前位置的权重和
	if(F[x][y]==-1){//判断（x,y） 是否已经求出f[x][y] ;
		if(x==n)F[x][y]=A[x][y];
		else{
			F[x][y]=max(Dfs(x+1,y),Dfs(x+1,y+1))+A[x][y];
		}
	}
	return F[x][y];
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++){
			cin>>A[i][j];
			F[i][j]=-1;
		}
	ans=0;
	Dfs(1,1);
	cout<<F[1][1]<<endl;
	return 0;
}

#include<bits/stdc++.h>//万能头文件，永远滴神
using namespace std;//命名空间
int a[1010][1010], n, ans;
//a是用来存输入的
//n是层数
//ans是权值最大值（答案）
void dfs(int x,int y,int c){//深搜
//x代表走到了第几层
//y代表走到了第几个
//c是用来求每一条路线的权值
	if(x==n){//判断是否到达边界
		if(c>ans){//打擂台
			ans=c;
		}
		return;//结束
	}
	dfs(x+1,y,c+a[x+1][y]);
	//左下搜索
	dfs(x+1,y+1,c+a[x+1][y+1]);
	//右下搜索
}
int main() {
	cin >> n;
	//输入
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cin >> a[i][j];
		}
	}//输入
	dfs(1,1,a[1][1]);//开始搜索
	cout<<ans;//输出答案
	return 0;//华丽丽的结束
}

#include<bits/stdc++.h>//头文件 
using namespace std;//命名空间 
const int N=1e6+10;//数组大小
int a[N][N],n,ans=0;//塔的数组，塔大小
void dfs(int x,int y,int curr){//坐标，权值
	if(x==n){//是否到达边界
		if(curr>ans)ans=curr;//擂台法
		return;//结束搜索
	}
	dfs(x+1,y,curr+a[x+1][y]);//搜索左下方数字
	dfs(x+1,y+1,curr+a[x+1][y+1]);//搜索右下方数字
}
int main(){//主函数
	cin>>n;//输入塔大小
	for(int i=1;i<=n;i++){//行数
		for(int j=1;j<=i;j++)cin>>a[i][j];//输入塔
	}
   	dfs(1,1,a[1][1]);//判断最大值
	cout<<ans;//输出 
	return 0;//结束 
}

#include<bits/stdc++.h>//头文件 using namespace std;//命名空间 const int N=1e6+10;//数组大小 int a[N][N],n,ans=0;//塔的数组，塔大小 void dfs(int x,int y,int curr){//坐标，权值 if(x==n){//是否到达边界 if(curr>ans)ans=curr;//擂台法 return;//结束搜索 } dfs(x+1,y,curr+a[x+1][y]);//搜索左下方数字 dfs(x+1,y+1,curr+a[x+1][y+1]);//搜索右下方数字 } int main(){//主函数 cin>>n;//输入塔大小 for(int i=1;i<=n;i++){//行数 for(int j=1;j<=i;j++)cin>>a[i][j];//输入塔 } dfs(1,1,a[1][1]);//判断最大值 cout<<ans;//输出 return 0;//结束 }

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int A[N][N],F[N][N],n,ans;
//定义数组A变量 n,ans 

void Dfs(int x,int y,int Curr){
// x代表走到了数字塔的第几层
// y代表走到了数字塔的第几个
// Curr代表走到当前位置的权重和
	if(x==n){//判断走到底层（边界） 
		if(Curr>ans)ans=Curr;//擂台法求最大值 
		return;
	}
	Dfs(x+1,y,Curr+A[x+1][y]);//走向下方 
	Dfs(x+1,y+1,Curr+A[x+1][y+1]);//走向右下方 
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)cin>>A[i][j];
	ans=0;
	Dfs(1,1,A[1][1]);
	cout<<ans<<endl;
	return 0;
}

#include<bits/stdc++.h> using namespace std; const int N=1e4+10; int A[N][N],F[N][N],n,ans; //定义数组变量

void Dfs(int x,int y,int Curr){ // x代表走到了数字塔的第几层 // y代表走到了数字塔的第几个 // Curr代表走到当前位置的权重和 if(x==n){//判断走到底层（边界） if(Curr>ans)ans=Curr;//擂台法求最大值 return; } Dfs(x+1,y,Curr+A[x+1][y]);//走向下方 Dfs(x+1,y+1,Curr+A[x+1][y+1]);//走向右下方 }

int main(){ cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++)cin>>A[i][j]; ans=0; Dfs(1,1,A[1][1]); cout<<ans<<endl; return 0; }

#include<bits/stdc++.h> using namespace std; const int N = 110; const int MAXN=1005; int A[MAXN][MAXN],F[MAXN][MAXN],N,Ans;

void bfs(int x,int yint Curr){ // x代表走到了数字塔的第几层 // y代表走到了数字塔的第几个 // Curr代表走到当前位置的权重和 if(x==N){//判断走到底层（边界） if(Curr>Ans)Ans=Curr;//擂台法求最大值 return; } Dfs(x+1,y,Curr+A[x+1][y]);//走向下方 Dfs(x+1,y+1,Curr+A[x+1][y+1]);//走向右下方 }

int main(){ cin>>N; for(int i=1;i<=N;i++) for(int j=1;j<=i;j++) cin>>A[i][j]; Ans =0; Dfs(1,1,A[1][1]); cout<<Ans<<endl; return 0; }

#include<bits/stdc++.h>//头文件
using namespace std;//命名空间
const int N=1e6+10;//数组大小
int a[N][N],n,ans=0;//储存数字塔的数组，数字塔大小，答案
void dfs(int x,int y,int curr){//数字坐标，权值
	if(x==n){//判断是否到达边界
		if(curr>ans)ans=curr;//擂台法
		return;//结束搜索
	}
	dfs(x+1,y,curr+a[x+1][y]);//搜索左下方数字
	dfs(x+1,y+1,curr+a[x+1][y+1]);//搜索右下方数字
}
int main(){//主函数
	cin>>n;//输入数字塔大小
	for(int i=1;i<=n;i++){//行数
		for(int j=1;j<=i;j++)cin>>a[i][j];//输入数字塔
	}
   	dfs(1,1,a[1][1]);//判断最大值
	cout<<ans;//输出答案
	return 0;//结束程序
}