Bỏ qua đến nội dung

MATRIXA

Mã bài: free034 Nhóm: Uncategorized Dạng bài: Undefined

Giới hạn thời gian
1,0 s
Giới hạn bộ nhớ
256 MB
Điểm
100
Tỉ lệ AC
25,0%
Người giải
3

Bạn có một bảng số A gồm m hàng và n cột, mỗi ô trong bảng có chứa một số nguyên. Gọi D(x, y, u, v) (1 \le x < u \le m, 1 \le y < v \le n) là tổng bao quanh hình chữ nhật có đỉnh trái trên là (x, y) và đỉnh phải dưới là (u, v). Nói cách khác, D(x, y, u, v) là tổng của các ô (i, j) thỏa mãn x \le i \le u, y \le j \le v và ít nhất một trong các điều kiện sau:

  • i = x
  • i = u
  • j = y
  • j = v

Nhiệm vụ của bạn là tìm giá trị D(x, y, u, v) lớn nhất có thể.

Input

  • Dòng đầu tiên chứa hai số nguyên dương m, n (2 \le m, n \le 300) - số hàng và số cột của bảng số A.
  • m dòng tiếp theo, mỗi dòng gồm n số nguyên có giá trị từ -10 đến 10 biểu diễn bảng số A.

Output

  • Một dòng duy nhất là giá trị lớn nhất của D(x, y, u, v).

Samples

Sample Input 1
3 3
-5 -9 9
-8 -6 7
-10 7 5
Sample Output 1
13
Sample Input 2
3 4
1 1 1 1
1 -5 -5 1
1 1 1 1
Sample Output 2
10

Scoring

  • 30\% số test có m, n \le 30;
  • 30\% số test khác có m, n \le 100;
  • 40\% số test còn lại không giới hạn gì thêm.

Bình luận