#include <iostream>
#include <cstdio>       /* printf() */
#include <cstdlib>      /* exit()   */

#define HEIGHT_LOWER_LIMIT 2
#define HEIGHT_UPPER_LIMIT 50
#define WIDTH_LOWER_LIMIT  2
#define WIDTH_UPPER_LIMIT  50

/* Error status */
#define ILLEGAL_MAPSIZE         1
#define ILLEGAL_CICADA_COUNT    2

class Cicada
{
public:
    void initialize(void)
    {
        /* 蝉分布図のサイズを取得 */
        std::cin >> maxHeight >> maxWidth;
        
        /* 制約チェック */
        if( (maxHeight < HEIGHT_LOWER_LIMIT) || (maxHeight > HEIGHT_UPPER_LIMIT)
         || (maxWidth < WIDTH_LOWER_LIMIT)   || (maxWidth > WIDTH_UPPER_LIMIT)  )
        {
            exit(ILLEGAL_MAPSIZE);
        }
        
        /* 蝉分布、計算結果の初期化 */
        for(int i=0; i<maxWidth; ++i)
        {
            cicadaMap[i] = 0;
            forwardBlocks[i] = 0;
            backwardBlocks[i] = 0;
        }
        return;
    }
    
    void search(void)
    {
        /* 蝉分布図を1行ごとに分割、各ブロックの蝉に出会う回数を計算 */
        for(unsigned int i = 0; i < maxHeight; ++i)
        {
            getMap();
            copyBlocks();
            calculate(i);
        }
        return;
    }
    
    void showResult(void)
    {
        /* 学校は蝉分布図の右下コーナーのブロック */
        printf("%d\n", forwardBlocks[maxWidth-1]);
        return;
    }
    
private:
    unsigned int maxHeight;
    unsigned int maxWidth;
    unsigned int cicadaMap[WIDTH_UPPER_LIMIT];      /* 1行分の蝉分布 */
    unsigned int forwardBlocks[WIDTH_UPPER_LIMIT];  /* 走査中の各ブロックにたどり着くまでに出会う最小の蝉総数 */
    unsigned int backwardBlocks[WIDTH_UPPER_LIMIT]; /* 走査中の各ブロックの一つ上の行の蝉総数 */
    
    /* 蝉分布図1行分を取得 */
    void getMap(void)
    {
        char character;
        for(int i=0; i<maxWidth; ++i)
        {
            std::cin >> character;
            cicadaMap[i] = ctoi(character);
        }
        return;
    }
    
    /* 1文字を整数1文字に変換 */
    unsigned int ctoi(char character)
    {
        unsigned int result = 0;
        if((character >= '0') && (character <= '9'))
        {
            result = character - '0';
        }
        else
        {
            exit(ILLEGAL_CICADA_COUNT);
        }
        return result;
    }
    
    /* 次の行の計算に使用するため結果をコピー */
    void copyBlocks(void)
    {
        for(int i = 0; i < maxWidth; ++i)
        {
            backwardBlocks[i] = forwardBlocks[i];
        }
        return;
    }
    
    /* 注目している1行の各ブロックへたどり着くまでに出会う蝉の最小数を計算 */
    void calculate(unsigned int row)
    {
        /* 西の端は北方向からしか移動できないので比較しない */
        forwardBlocks[0] = backwardBlocks[0] + cicadaMap[0];
        
        if(row == 0)    /* 北の端は西方向からしか移動できないので比較しない */
        {
            for(int i = 1; i < maxWidth; ++i)
            {
                forwardBlocks[i] = forwardBlocks[i-1] + cicadaMap[i];
            }
        }
        else
        {
            for(int i = 1; i < maxWidth; ++i)
            {
                /* 蝉が少ない方の結果を格納 */
                if(forwardBlocks[i-1] < backwardBlocks[i])    /* 西方向 < 北方向 */
                {
                    forwardBlocks[i] = forwardBlocks[i-1] + cicadaMap[i];
                }
                else
                {
                    forwardBlocks[i] = backwardBlocks[i] + cicadaMap[i];
                }
            }
        }
        return;
    }
    
};

int main(void)
{
    Cicada cicada;
    
    cicada.initialize();
    cicada.search();
    cicada.showResult();
    
    return 0;
}


Measured memory_bytes: 3216