/* -*- coding: utf-8 -*- * * 2982.cc: No.2982 Logic Battle - yukicoder */ #include #include #include using namespace std; /* constant */ const int MAX_N = 5000; /* typedef */ using ll = long long; using pll = pair; /* global variables */ int as[MAX_N][3]; pll dp[MAX_N + 1][3]; /* subroutines */ template inline void setmax(T &a, T b) { if (a < b) a = b; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < 3; j++) scanf("%d", as[i] + j); for (int i = 0; i < n; i++) for (int j = 0; j < 3; j++) { int j1 = (j + 1) % 3, j2 = (j + 2) % 3; auto [s1, x1] = dp[i][j1]; auto [s2, x2] = dp[i][j2]; ll d1 = s1 + x1 + as[i][j], d2 = s2 + x2 + as[i][j]; if (d1 >= d2) dp[i + 1][j] = {d1, max(0LL, x1 + as[i][j] - 1)}; else dp[i + 1][j] = {d2, max(0LL, x2 + as[i][j] - 1)}; } ll maxd = max(dp[n][0].first, max(dp[n][1].first, dp[n][2].first)); printf("%lld\n", maxd); return 0; }