Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

BGH nhà trường đang có kế hoạch làm mái che sân trường để có điều kiện thời tiết thuận lợi tổ chức các chương trình ngoài sân trường. Sân trường là một hình chữ nhật kích thước ~m \times n~ được chia thành lưới ô vuông ~m~ hàng, ~n~ cột. Một số ô trên sân trường có đang trồng cây (mỗi ô nếu có cây thì chỉ có một cây). BGH muốn làm một mái che là một hình chữ nhật con nằm trong sân trường có các cạnh song song với các cạnh sân trường và có diện tích bằng đúng ~k~ ô vuông. Mong muốn của BGH là số lượng cây nằm dưới mái che là ít nhất có thể. Em hãy giúp BGH tính số lượng ít nhất các cây nằm dưới mái che.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương ~m, n, k~ được ghi cách nhau bởi dấu cách;
• ~m~ dòng sau, mỗi dòng chứa một xâu ký tự độ dài ~n~ chỉ gồm các ký tự 0, 1 mô tả một hàng của sân trường (ký tự 0 tương ứng với không có cây, ký tự 1 tương ứng với có cây).

Kết quả

• Một số nguyên duy nhất là số lượng ít nhất các cây nằm dưới mái che. Nếu không thể làm được mái che với diện tích đúng bằng ~k~ thì ghi ra ~-1~.

Giới hạn

Trong tất cả các test: ~1 \le m, n \le 500~; ~k \le m \times n~.

Subtask

• Subtask #1: ~40\%~ số điểm có ~m, n \le 20~;
• Subtask #2: ~30\%~ số điểm có ~m, n \le 50~;
• Subtask #3: ~30\%~ số điểm còn lại không có ràng buộc gì thêm.

Sample Input 1

3 4 6
0110
1000
1001

Sample Output 1

1

Giải thích

Làm mái che là hình chữ nhật ~2 \times 3~ có ô trên trái là ~(2, 2)~, dưới phải là ~(3, 4)~, có diện tích bằng ~6~ và chỉ chứa duy nhất một cây ở ô ~(3, 4)~.

Nguồn: LuyenCode (COVER).