Xét ma trận A có m hàng và n cột, các hàng được đánh chỉ số từ 1 đến m theo thứ tự từ trên xuống dưới, các cột được đánh chi số từ 1 đến n theo thứ tự từ trái sang phải. Kí hiệu A(i,j) là giá trị của phần tử nằm giao giữa hàng i và cột j (1 ≤ i <= m; 1 ≤ j <= n).

Có hai thao tác rút gọn ma trận theo hàng và theo cột.

1) Thao tác rút gọn theo hàng: chọn hai hàng i và i + 1 (1 ≤ i < m) mà tổng các phần từ trên hàng i bằng tổng các phần tử trên hàng i + 1, việc rút gọn hàng i và i + 1 theo các bước sau:

Bước 1: Thay đổi giá trị các phần tử trên hàng i: A(i, j) = A(i, j) + A(i + 1, j) với 1 ≤ j <= n;

Bước 2: Xóa hàng i + 1 khỏi ma trận, khi đó số hàng của ma trận giảm đi một và các hàng được đánh chi số lại bắt đầu từ 1 từ trên xuống dưới.

2) Thao tác rút gọn theo cột: chọn hai cột j và j + 1 (1 ≤ j < n) mà tổng các phần tử trên cột j bằng tổng các phần tử trên cột j + 1, việc rút gọn cột j và j + 1 theo các bước sau:

Bước 1: Thay đổi giá trị các phần tử trên cột j: A(i,j) = A(i,j) + A(i,j + 1) với 1 <= i ≤ m;

Bước 2: Xóa cột j + 1 khỏi ma trận, khi đó số cột của ma trận giảm đi một và các cột được đánh chi số lại bắt đầu từ 1 từ trái sang phải.

Yêu cầu: Cho ma trận A, hãy tìm một dãy các thao tác rút gọn để nhận được ma trận có số lượng phần từ là ít nhất.

Dữ liệu: Vảo từ file văn bản RMAT.INP:

• Dòng đầu tiên chứa hai số nguyên dương m và n là số hàng và số cột của ma trận;

• Dòng thứ i (1 <= i <= m) trong số m dòng tiếp theo chứa n số nguyên, mỗi số có giá trị tuyệt đổi không vượt quá 10^6, số thứ j (1 ≤ j <= n) là giá trị A(i, j).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản RMAT.OUT một số nguyên duy nhất là số lượng phần tử còn lại trong phương án thực hiện dây các thao tác rút gọn tim được.

Ràng buộc:

• Có 30% số test ứng với 30% số điểm của bải thoa mẫn: m = 1 và n ≤ 10;

• 20% số test khác ứng với 20% số điểm của bài thóa mãn: m = 1 và n ≤ 100;

• 30% số test khác ứng với 30% số điểm của bài thóa mãn: m x n ≤ 500;

• 10% số test khác ứng với 10% số điểm của bài thóa mãn: m x n ≤ 5000;

• 10% số test còn lại ứng với 10% số điểm của bài thoa măn: m x n ≤ 10^6

Input:

3 5
1 2 3 4 5
5 4 3 2 1
4 -1 -1 -1 2

Output:

6

Giải thích: Dãy các thao tác rút gọn như sau:

• Rút gọn hàng 1 và hàng 2 đế nhận được ma trận:

6 6 6 6 6

4 -1 -1 -1 2

• Rút gọn cột 2 và cột 3 để nhận được ma trận:

6 12 6 6

4 -2 -1 2

• Rút gọn cột 1 và cột 2 đề nhận được ma trận:

18 6 6

2 -1 2

Không thục hiện được thêm thao tác rất gọn.

Số lượng phần tử của ma trận thu được là 6.