Rút gọn ma trận

Xét ma trận $A$ gồm $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 chỉ 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\le i\le m;1\le j\le n)$.

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

Thao tác rút gọn theo hàng: chọn hai hàng $i$ và $i+1$ $(1\le 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\le j\le 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 chỉ số lại bắt đầu từ $1$ từ trên xuống dưới.

Thao tác rút gọn theo cột: chọn hai cột $j$ và $j+1$ $(1\le 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\le i\le 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 chỉ 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

• Dòng đầu tiên chứa $2$ 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\le i\le 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\le j\le 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.

Dữ liệu ra

In ra 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 tìm được.

Ràng buộc

• $m\times n\le {10}^6$.
• $|A(i,j)|\le {10}^6$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $m=1$ và $n\le 10$.
• Subtask 2 ($20\%$ số điểm): $m=1$ và $n\le 100$.
• Subtask 3 ($30\%$ số điểm): $m\times n\le 500$.
• Subtask 4 ($10\%$ số điểm): $m\times n\le 5000$.
• Subtask 5 ($10\%$ số điểm): $m\times n\le {10}^6$.

Ví dụ