#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<double> CMP;
class WallGameDiv1 { public:
int play(vector <string> costs)
{
int H = costs.size();
int W = costs[0].size();
vector<vector<int> > C(H, vector<int>(W));
for(int y=0; y<H; ++y)
for(int x=0; x<W; ++x)
C[y][x] = costs[y][x] = '0';
vector<vector<int> > dp(H, vector<int>(W));
for(int x=0; x<W; ++x)
dp[H-1][x] = C[H-1][x];
// dp[y][x] = what is the score of entering C[y] from [x]??
for(int y=H-2; y>=0; --y)
for(int x=0; x<W; ++x)
{
int le = lefty(C[y], dp[y+1], x);
vector<int> CC = C[y], DD = dp[y+1];
reverse(CC.begin(), CC.end());
reverse(DD.begin(), DD.end());
int ri = lefty(CC, DD, W-1-x);
if(min(le, ri) < dp[y+1][x])
dp[y][x] = C[y][x] + dp[y+1][x];
else
dp[y][x] = C[y][x] + min(le, ri);
// no blocking score
vector<int> s = dp[y+1];
s[x] += C[y][x];
for(int p=C[y][x], xx=x-1; xx>=0; --xx)
s[xx] += (p += C[y][xx]);
for(int p=C[y][x], xx=x+1; xx<W; ++xx)
s[xx] += (p += C[y][xx]);
}
return *min_element(dp[0].begin(), dp[0].end());
}
int lefty(const vector<int>& cur, const vector<int>& down, const int S)
{
// best score when moved to left from S first;
return -1;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, WallGameDiv1().play(costs));}
int main(){
CASE(0)
string costs_[] = {"12"
,"34"};
vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
int _ = 6;
END
CASE(1)
string costs_[] = {"99999"
,"99999"
,"99999"};
vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
int _ = 99;
END
CASE(2)
string costs_[] = {"11111"
,"90005"};
vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
int _ = 10;
END
CASE(3)
string costs_[] = {"4417231387449337370319219832088987579792"
,"3117295688208899006196193430472892512797"
,"0835796222361526836944954410684516919758"
,"1988200069973565052900745230547016216225"
,"8080511471118865780390486996601082102418"
,"4229084185957675819725844582167613108400"
,"9068653877952162764545674979144308771754"
,"8551565425951612499712254182109991511690"
,"7090525592007482152807163656647658543093"
,"9198968742256995592729889137556032960142"
,"2071864379877766468141740053503050313101"
,"1055375249261868472993219156394129253481"
,"2461178270502857106406495509025426298874"
,"8216781259733537757203421037984512664825"
,"4693452554407216935375049784445568498482"
,"2709693439640250842244170297203200674391"
,"5122217695676372684217182241705137947908"
,"6668814191410691246849638388008228444294"
,"4952122070212780440963814752538149378639"
,"9827737761436134120332969866554332504400"
,"3412406588339828249986707470540386748886"
,"7521506848088506994554600408372456405830"
,"1916926179183007872881163173153907665999"
,"6636166791472761992310264951474925339024"
,"6679667717747231380196787943691121008076"
,"3218993234115685151069259138068533004433"
,"4920152552986426962081492913852060211795"
,"0365186235986445521382132973036266396894"
,"3205351414936828189305188614651974318855"
,"3144278971529524658788277656125598825426"
,"5525287537572356662391582052968411726245"
,"2130137226726919525622574701068062252930"
,"2369996694245544770519574837226971226841"
,"6806769058165410189286521891570936341547"
,"0448109211631660241710734664066810078242"
,"4622919135804954122810530631429501069659"
,"0235247446548732490429856705369583140671"
,"2193399741215975228987754171460722199304"
,"1203037020703833716225328076959743850915"
,"5419885193880826109484912489603262199432"};
vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
int _ = 7366;
END
CASE(4)
string costs_[] = ;
vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
int _ = ;
END
CASE(5)
string costs_[] = ;
vector <string> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_));
int _ = ;
END
}
// END CUT HERE