Yandex E

#include <iostream>
#include <numeric>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <vector>
#include <string>
using namespace std;

typedef long long ll;

const int MAXN = 100;
const int INF = 1000000000;

char buf[MAXN+1];

int a[MAXN][MAXN];
int rowSum[MAXN][MAXN+1];

int dp[2][MAXN+1][MAXN*MAXN+1];
int minDp[MAXN+1][MAXN*MAXN+1];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%s", buf);
        for(int j=0;j<m;j++)
            a[i][j] = buf[j]-'0';
    }

    int total = 0;
    for(int i=0;i<n;i++)
    {
        rowSum[i][0]=0;
        for(int j=0;j<m;j++)
            rowSum[i][j+1] = rowSum[i][j] + a[i][j];

        total += rowSum[i][m];
    }

    int t=0;
    for(int i=0;i<=m;i++)
        for(int j=0;j<=total;j++)
            dp[t][i][j] = INF;
    dp[t][m][total] = 0;

    for(int k=n-1;k>=0;k--, t=1-t)
    {
        for(int i=0;i<=m;i++)
            for(int j=0;j<=total;j++)
                dp[1-t][i][j] = INF;

        for(int j=0;j<=total;j++)
        {
            minDp[m][j] = dp[t][m][j];
            for(int i=m-1;i>=0;i--)
                minDp[i][j] = min(minDp[i+1][j], dp[t][i][j]);
        }

        for(int j=0;j<=total;j++)
        {
            for(int i=0;i<=m && i+j<=total;i++)
            {
//              dp[1-t][i][j] = INF;
//              for(int c=i;c<=m;c++)
//                  dp[1-t][i][j] = min(dp[1-t][i][j], dp[t][c][j+i] + rowSum[k][m-i]);
                dp[1-t][i][j] = min(INF, minDp[i][j+i] + rowSum[k][m-i]);
            }
        }
    }

    int res = INF;
    for(int i=0;i<=m;i++)
        res = min(res, dp[t][i][0]);

    printf("%d\n", res);

    return 0;
}