Trò chơi kỳ lạ trên ma trận

Cho ma trận $a$ gồm $n$ hàng và $m$ cột, mỗi phần tử là $0$ hoặc $1$. Hàng và cột được đánh số từ $1$.

Bạn được phép thay một số ô mang giá trị $1$ trong ma trận thành $0$ (số ô thay là tùy ý, có thể không thay ô nào). Sau khi thay xong, điểm số được tính như sau:

1. Ban đầu điểm số bằng $0$.
2. Với mỗi cột $j$, tìm ô mang giá trị $1$ nằm cao nhất, tức là hàng $i$ nhỏ nhất thỏa mãn $a_{i,j}=1$. Nếu cột $j$ không còn ô nào mang giá trị $1$ thì bỏ qua cột này.
3. Xét $min(k,n-i+1)$ ô liên tiếp trong cột $j$ tính từ ô vừa tìm được, tức là các hàng $i,i+1,\dots ,min(n,i+k-1)$, rồi đếm số ô mang giá trị $1$ trong đó. Cộng số đếm được vào điểm số.

Hãy tìm điểm số lớn nhất có thể đạt được, và trong tất cả các cách thay đạt được điểm số lớn nhất đó, hãy tìm số ô bị thay ít nhất.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa $m$ số nguyên là các phần tử của hàng thứ $i$ của ma trận. Mỗi số là $0$ hoặc $1$.

Dữ liệu ra

Một dòng chứa hai số nguyên: điểm số lớn nhất có thể đạt được và số ô cần thay ít nhất để đạt được điểm số đó.

Ràng buộc

• $1\le k\le n\le 100$
• $1\le m\le 100$
• $a_{i,j}\in \{0,1\}$

Ví dụ