#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
#define INVALID_NUMBER      0xF

enum errorStatus
{
    kIllegal_MapSize   = 1,
    kIllegal_CicadaCnt = 2,
};

class Cicada
{
public:
    Cicada()
    {
        /* 各メンバ変数の初期化 */
        for(int i = 0; i < WIDTH_UPPER_LIMIT; ++i)
        {
            cicadaMap[i] = 0;
            forwardBlocks[i] = 0;
            backwardBlocks[i] = 0;
        }
    }
    
    ~Cicada(){;}
    
    void search(void)
    {
        inputMapSize();     /* 蝉分布図のサイズを取得 */
        
        /* 蝉分布図を1行ごとに分割、各ブロックの蝉に出会う回数を計算 */
        for(int i = 0; i < maxHeight; ++i)
        {
            inputMap();     /* 蝉分布図1行分を取得 */
            calculate(i);   /* 探索する1行の各ブロックへたどり着くまでに出会う蝉の最小数を計算 */
            copyBlocks();   /* 探索結果を次の1行分の探索で使用するために複製 */
        }
        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]; /* 探索中の各ブロックの一つ上の行の蝉総数 */
    
    /* 蝉分布図のサイズを取得 */
    void inputMapSize(void)
    {
        std::cin >> maxHeight >> maxWidth;
        
        /* 制約チェック */
        if( (maxHeight < HEIGHT_LOWER_LIMIT) || (maxHeight > HEIGHT_UPPER_LIMIT)
         || (maxWidth < WIDTH_LOWER_LIMIT)   || (maxWidth > WIDTH_UPPER_LIMIT)  )
        {
            exit(kIllegal_MapSize);
        }
        return;
    }
    
    /* 蝉分布図1行分を取得 */
    void inputMap(void)
    {
        char character;
        for(int i=0; i<maxWidth; ++i)
        {
            std::cin >> character;
            cicadaMap[i] = ctoi(character);
            
            /* 制約チェック */
            if(cicadaMap[i] == INVALID_NUMBER)
            {
                exit(kIllegal_CicadaCnt);
            }
        }
        return;
    }
    
    /* 1文字を整数1文字に変換 */
    unsigned int ctoi(char character)
    {
        unsigned int result = INVALID_NUMBER;
        /* 半角数字以外は不正 */
        if((character >= '0') && (character <= '9'))
        {
            result = character - '0';
        }
        return result;
    }
    
    /* 探索結果を次の1行分の探索で使用するために複製 */
    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];
        
        for(int i = 1; i < maxWidth; ++i)
        {
            /* 蝉が少ないルートの結果を格納 */
            if( (row == 0)  /* 北の端は西方向からしか移動できないので比較しない */
             || (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.search();
    cicada.showResult();
    
    return 0;
}



Measured memory_bytes: 3220