https://www.luogu.com.cn/problem/P1130

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[2010][2010];
int dp[2020][2020];

int n,m;

signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%lld",&a[i][j]);
	int mx=1145141919;
	for(int i=1;i<=m;i++) dp[i][1]=a[i][1];
	for(int i=2;i<=n;i++)
	{
		dp[1][i]=min(dp[1][i-1],dp[2][i-1])+a[1][i];
		dp[m][i]=min(dp[m][i-1],dp[1][i-1])+a[m][i];
		for(int j=2;j<m;j++)
		{
			dp[j][i]=min(dp[j][i-1],dp[j+1][i-1])+a[j][i];
		}
	}
	for(int i=1;i<=m;i++) mx=min(mx,dp[i][n]);
	printf("%lld",mx);
}