#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define BIT(nr) (1ULL << (nr)) #define int long long #define ll long long #define double long double #define mod 1000000007 #define MAXN (int)1e+5 * 2+1 #define LL_MAX 9223372036854775807 #define LL_HALFMAX 9223372036854775807 / 2 #define MIN -(9223372036854775807 / 2) #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() #define REPS(i,x) for(int i=1;i<=(int)(x);i++) #define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--) #define RREPS(i,x) for(int i=((int)(x));i>0;i--) #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define mp make_pair template inline void chmin(T1& a, T2 b) { if (a > b) a = b; } template inline void chmax(T1& a, T2 b) { if (a < b) a = b; } using namespace std; using Weight = int; using Flow = int; struct Edge { int src, dst; // libalgo のものに追加、メンバを追加するだけなので互換性は崩さないはず、逆辺のG[e.dstの]インデックスを保持 int rev; Weight weight; Flow cap; Edge() : src(0), dst(0), weight(0) {} Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {} bool operator<(const Edge& right) const { return dst < right.dst; } }; using Edges = std::vector; using Graph = std::vector; using Array = std::vector; using Matrix = std::vector; void add_edge(Graph& g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); g[b].emplace_back(b, a, w); } void add_arc(Graph& g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); } int dx[4] = { 0, 1, 0, -1 }; // x軸方向への変位 int dy[4] = { 1, 0, -1, 0 }; // y軸方向への変位 struct uf_tree { std::vector parent; int __size; uf_tree(int size_) : parent(size_, -1), __size(size_) {} void unite(int x, int y) { if ((x = find(x)) != (y = find(y))) { if (parent[y] < parent[x]) std::swap(x, y); parent[x] += parent[y]; parent[y] = x; __size--; } } bool is_same(int x, int y) { return find(x) == find(y); } int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); } int size(int x) { return -parent[find(x)]; } int size() { return __size; } }; class Vector3D { public: double x, y, z; Vector3D(double x, double y, double z) { this->x = x; this->y = y; this->z = z; } Vector3D operator- (Vector3D right) { return Vector3D(right.x - x, right.y - y, right.z - z); } double Length() { return sqrtl(x * x + y * y + z * z); } }; bool solve() { return false; } int mod_pow(int x, int n, int mo) { int res = 1; while (n > 0) { if (n & 1LL) { res *= x; res %= mo; } x = x * x % mo; n >>= 1; } return res; } #ifdef DEBUG template ostream& operator<<(ostream& o, const vector& v) { o << "{"; for (int i = 0; i < (int)v.size(); i++)o << (i > 0 ? ", " : "") << v[i]; o << "}"; return o; } #endif // DEBUG template ostream& operator<<(ostream& o, const vector& v) { for (int i = 0; i < (int)v.size(); i++)o << (i > 0 ? " " : "") << v[i]; return o; } int dp[1010][2]; signed main() { int N, M; cin >> N >> M; vector a(N + 1, 0); REPS(i, N) { int su = 0; rep(j, M) { int ip; cin >> ip; su += ip; } a[i] = su; } // dp[i][j] := i(1-indexed)番目を見終わったとき、j(mod 2)回おかしを食べている時の最大スコア dp[0][0] = 0; rep(i, N) { // たべる chmax(dp[i + 1][1], dp[i][0] + a[i + 1]); chmax(dp[i + 1][0], dp[i][1] - a[i + 1]); // たべない chmax(dp[i + 1][0], dp[i][0]); chmax(dp[i + 1][1], dp[i][1]); } cout << max(dp[N][0], dp[N][1]) << "\n"; }