Corona Warriors

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define vi vector<int>
#define N 2e5 + 5
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define forn(i, n) for (int i = 0; i < n; i++)
#define ll long long
#define init(arr) memset(arr, 0, sizeof(arr))
#define endl "\n"
#define mp make_pair

 int d,p;
 int dp[11][21];
 int eff[11][21];
    int solve(int di,int pi)
    {
        if(pi==p)
            return 0;

        if(dp[di][pi]!=-1)
            return dp[di][pi];

        if(di==d-1)
        {
            int ans=0;
            if(pi==0)
                ans=eff[di][p-1];
            else
                ans=eff[di][p-1]-eff[di][pi-1];
            return dp[di][pi] = ans;
        }

        int ans = INT_MAX;
        ans = min(solve(di+1,pi),ans);
        for(int i=pi;i<p;i++)
        {
            int temp=0;
            if(pi==0)
                temp=eff[di][i];
            else
                temp=eff[di][i]-eff[di][pi-1];
            ans = min(ans,min(temp+solve(di,pi+1),temp+solve(di+1,pi+1)));
        }
        return dp[di][pi] = (ans==INT_MAX)?0:ans;
    }
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>p>>d;
    for(int i=0;i<=10;i++)
        for(int j=0;j<=20;j++){
            dp[i][j]=-1;eff[i][j]=0;}

    for(int i=0;i<d;i++)
    {
        for(int j=0;j<p;j++)
            cin>>eff[i][j];
        for(int j=1;j<p;j++)
            eff[i][j]+=eff[i][j-1];
    }

    cout<<solve(0,0)<<endl;
}