Bạn nào hứng thú với các bài toán thuật toán thì thử sức với bài toán này nhé.

Có một nhà kho chứa hàng, các thùng hàng được chất chồng lên nhau thành từng trụ theo từng dòng, giống như cái mảng 2 chiều mỗi giá trị của từng phần tử trong mảng tượng trưng cho độ cao của các trụ hàng, trong nhà kho có 3 camera:

  • Camera phía trước: quét được các trụ hàng cao nhất trên từng cột của mảng
  • Camera bên cánh: quét được các trụ hàng cao nhất trên từng dòng của mảng
  • Camera trên trần nhà: quét được ô nào của mảng có cột hàng hoặc không

Sau mỗi giờ camera sẽ quét lại kho hàng, nếu nó nhận thấy có sự thay đổi thì sẽ báo động. Nhiệm vụ đặt ra là làm sao để tên trộm lấy được nhiều thùng hàng nhất có thể mà không bị camera phát hiện.

Input:
Dòng đầu tiên chứa 2 số integer r (1 ≤ r ≤ 100) và c (1 ≤ c ≤ 100), lần lượt là số dòng và số cột của mảng.
r dòng và c cột tiếp theo sẽ là giá trị tượng trưng cho độ cao của từng cột hàng h (0 ≤ h ≤ 10^9)

Output:
In ra số thùng hàng tối đa mà tên trộm có thể lấy mà không bị camera phát hiện.

Sample input:

5 5
1 4 0 5 2
2 1 2 0 1
0 2 3 4 4
0 3 0 3 1
1 2 2 1 1

Sample output:

9

Các bạn có thể submit bài tại link sau: http://r.grokking.org/forum-acm-improbable

Trích đề thi trong cuộc thi ACM quốc tế vòng final.