#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; namespace atcoder{};using namespace atcoder; using ull = uint64_t; using ll = int64_t; using vi = vector; using vll = vector; using vs = vector; using ld = long double; using P = pair; using G = vector>; #ifdef MYDEBUG #define LO(...) fprintf(stderr, __VA_ARGS__) #define debug(x) cerr << "\033[33m(line:" << __LINE__ << ") " << #x << ": " << x << "\033[m" << endl #else #define LO(...) (void)0 #define debug(x) (void)0 #endif #define reps(i,a,n) for(ll i##_len = (ll)(n), i = (a); i < i##_len; ++i) #define rep(i,n) reps(i,0,n) #define rrep(i,n) reps(i,1,n+1) #define repd(i,n) for(ll i=n-1;i>=0;i--) #define rrepd(i,n) for(ll i=n;i>=1;i--) #define inp(i) ll i; cin >> i; #define inps(s) string s; cin >> s; #define inpp(p) cin >> (p).first >> (p).second #define inpv(v,N) vll v(N);rep(i,N)cin>>v[i]; #define inpg(g,N,M) g.resize(N);rep(i,M){inp(a);inp(b);a--,b--;g[a].push_back(b);g[b].push_back(a);} #define all(v) begin(v),end(v) #define YESNO(b) cout<<(b?"YES\n":"NO\n") #define yesno(b) cout<<(b?"yes\n":"no\n") #define YesNo(b) cout<<(b?"Yes\n":"No\n") #define YES cout<<"YES\n" #define NO cout<<"NO\n" #define yes cout<<"yes\n" #define no cout<<"no\n" #define Yes cout<<"Yes\n" #define No cout<<"No\n" #define SP cout << " " #define ENDL cout << "\n" #define ou(i) cout << (i) #define ous(i) cout << (i) << " " #define oul(i) cout << (i) << "\n" #define setfp() cout << fixed << setprecision(16) template void ouv(const C &v){for(auto &&e:v){cout << e;if(&e != &v.back()) cout << ' ';}cout << "\n";} template void ouvadd(const C &v){for(auto &&e:v){cout << e+1;if(&e != &v.back()) cout << ' ';}cout << "\n";} templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b>a[i][j]; } } ll mn = 0; rep(i,N){ ll nex = 1e18; LO("i=%ld : ", i); rep(j,M){ ll sub = i?a[i-1][j]:0; dp[i+1][j] = min(dp[i][j] + a[i][j], mn + a[i][j] + sub); chmin(nex, dp[i+1][j]); LO("%ld ", dp[i+1][j]); } LO("\n"); mn = nex; } ll ans = 1e18; rep(i,M){ chmin(ans, dp[N][i]); } oul(ans); return 0; }