#include #include #include namespace nono { template class Matrix { public: Matrix() = default; Matrix(int row, int column): row_(row), column_(column), data_(row, std::vector(column)) {} Matrix(int row, int column, T elem): row_(row), column_(column), data_(row, std::vector(column, elem)) {} explicit Matrix(const std::vector>& data) : row_(data.size()), column_(data.front().size()), data_(data) { for (int i = 0; i < row_; i++) {} } Matrix(std::initializer_list> init): data_(init.begin(), init.end()) { row_ = data_.size(); column_ = data_.front().size(); for (int i = 0; i < row_; i++) {} } const std::vector& operator[](const int pos) const { return data_[pos]; } std::vector& operator[](const int pos) { return data_[pos]; } Matrix& operator+=(const T rhs) { for (int i = 0; i < row_; i++) { for (int j = 0; j < column_; j++) { data_[i][j] += rhs; } } return *this; } Matrix& operator-=(const T rhs) { for (int i = 0; i < row_; i++) { for (int j = 0; j < column_; j++) { data_[i][j] -= rhs; } } return *this; } Matrix& operator*=(const T rhs) { for (int i = 0; i < row_; i++) { for (int j = 0; j < column_; j++) { data_[i][j] *= rhs; } } return *this; } Matrix& operator/=(const T rhs) { for (int i = 0; i < row_; i++) { for (int j = 0; j < column_; j++) { data_[i][j] /= rhs; } } return *this; } friend Matrix operator+(const Matrix& lhs, const T rhs) { return Matrix(lhs) += rhs; } friend Matrix operator+(const T lhs, const Matrix& rhs) { return Matrix(rhs) += lhs; } friend Matrix operator-(const Matrix& lhs, const T rhs) { return Matrix(lhs) -= rhs; } friend Matrix operator-(const T lhs, const Matrix& rhs) { return Matrix(rhs) -= lhs; } friend Matrix operator*(const Matrix& lhs, const T rhs) { return Matrix(lhs) *= rhs; } friend Matrix operator*(const T lhs, const Matrix& rhs) { return Matrix(rhs) *= lhs; } friend Matrix operator/(const Matrix& lhs, const T rhs) { return Matrix(lhs) /= rhs; } friend Matrix operator/(const T lhs, const Matrix& rhs) { return Matrix(rhs) /= lhs; } Matrix& operator+=(const Matrix& rhs) { for (int i = 0; i < row_; i++) { for (int j = 0; j < column_; j++) { data_[i][j] += rhs.data_[i][j]; } } return *this; } Matrix& operator-=(const Matrix& rhs) { for (int i = 0; i < row_; i++) { for (int j = 0; j < column_; j++) { data_[i][j] -= rhs.data_[i][j]; } } return *this; } Matrix& operator*=(const Matrix& rhs) { std::vector> mat(row_, std::vector(rhs.column_)); for (int i = 0; i < row_; i++) { for (int k = 0; k < column_; k++) { for (int j = 0; j < rhs.column_; j++) { mat[i][j] += data_[i][k] * rhs.data_[k][j]; } } } data_ = std::move(mat); column_ = rhs.column_; return *this; } friend Matrix operator+(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) += rhs; } friend Matrix operator-(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) -= rhs; } friend Matrix operator*(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) *= rhs; } [[nodiscard]] Matrix pow(long long exp) const { Matrix result(row_, column_); Matrix base(*this); for (int i = 0; i < row_; i++) { result[i][i] = static_cast(1); } while (exp > 0) { if (exp & 1) { result *= base; } base *= base; exp >>= 1; } return result; } [[nodiscard]] Matrix rotate() { std::vector> result(column_, std::vector(row_)); for (int i = 0; i < row_; i++) { for (int j = 0; j < column_; j++) { result[j][row_ - i - 1] = data_[i][j]; } } return Matrix(result); } [[nodiscard]] Matrix transpose() { std::vector> result(column_, std::vector(row_)); for (int i = 0; i < row_; i++) { for (int j = 0; j < column_; j++) { result[j][i] = data_[i][j]; } } return Matrix(result); } int row() { return row_; } int column() { return column_; } private: int row_, column_; std::vector> data_; }; } // namespace nono namespace nono { struct Init {}; void solve([[maybe_unused]] const Init& init) { int h, w; std::cin >> h >> w; Matrix a(h, w); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { std::cin >> a[i][j]; } } int ans = 0; std::vector row(h); std::vector column(h); std::vector naname1(h + w - 1); std::vector naname2(h + w - 1); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { row[i] += a[i][j]; column[j] += a[i][j]; naname1[i + j] += a[i][j]; naname2[h - 1 - i + j] += a[i][j]; } } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { ans = std::max(ans, row[i] + column[j] - a[i][j]); } } for (int i = 0; i < h; i++) { for (int k = 0; k + 1 < h + w - 1; k++) { int j = k - i; if (0 <= j && j < w) { ans = std::max(ans, row[i] + naname1[k] - a[i][j]); } else { ans = std::max(ans, row[i] + naname1[k]); } } } for (int i = 0; i < h; i++) { for (int k = 0; k + 1 < h + w - 1; k++) { int j = k - h + 1 + i; if (0 <= j && j < w) { ans = std::max(ans, row[i] + naname2[k] - a[i][j]); } else { ans = std::max(ans, row[i] + naname2[k]); } } } for (int j = 0; j < w; j++) { for (int k = 0; k + 1 < h + w - 1; k++) { int i = k - j; if (0 <= i && i < h) { ans = std::max(ans, column[j] + naname1[k] - a[i][j]); } else { ans = std::max(ans, column[j] + naname1[k]); } } } for (int j = 0; j < w; j++) { for (int k = 0; k + 1 < h + w - 1; k++) { int i = h - 1 + j - k; if (0 <= i && i < h) { ans = std::max(ans, column[j] + naname1[k] - a[i][j]); } else { ans = std::max(ans, column[j] + naname1[k]); } } } for (int k1 = 0; k1 + 1 < h + w - 1; k1++) { for (int k2 = 0; k2 + 1 < h + w - 1; k2++) { bool flag = false; if ((k1 + k2 - h + 1) % 2 == 0) { int j = (k1 + k2 - h + 1) / 2; int i = k1 - j; if (0 <= i && i < h && 0 <= j && j < w) { flag = true; ans = std::max(ans, naname1[k1] + naname2[k2] - a[i][j]); } } if (!flag) { ans = std::max(ans, naname1[k1] + naname2[k2]); } } } std::ranges::sort(row, std::greater()); std::ranges::sort(column, std::greater()); std::ranges::sort(naname1, std::greater()); std::ranges::sort(naname2, std::greater()); ans = std::max(ans, row[0]); ans = std::max(ans, column[0]); ans = std::max(ans, naname1[0]); ans = std::max(ans, naname2[0]); if (row.size() > 1) ans = std::max(ans, row[0] + row[1]); if (column.size() > 1) ans = std::max(ans, column[0] + column[1]); if (naname1.size() > 1) ans = std::max(ans, naname1[0] + naname1[1]); if (naname2.size() > 1) ans = std::max(ans, naname2[0] + naname2[1]); std::cout << ans << std::endl; } } // namespace nono int main() { std::cin.tie(0)->sync_with_stdio(0); std::cout << std::fixed << std::setprecision(16); int t = 1; nono::Init init; while (t--) nono::solve(init); }