/***********************************************/
/* Volume22-2272 Cicada                        */
/***********************************************/
#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 */
/* Submit時にError Statusを0以外で返すとAOJは    */
/* 本来のエラー内容を見せてくれなくなるので一旦0 */
#define ILLEGAL_MAPSIZE 0
#define ILLEGAL_CICADA_COUNT 0

class Route
{
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();
            copy();
            calculate(i);
            
        }
        return;
    }
    
    void show(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 copy(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)
{
    Route route;
    
    route.initialize();
    route.search();
    route.show();
    
    return 0;
}


Measured memory_bytes: 3216