Trong một buổi sinh hoạt ngoại khóa, để tăng thêm phần hào hứng, ban tổ chức đã đưa ra trò chơi gấp giấy. Trò chơi bao gồm một tờ giấy hình vuông kích thước n x n được kẻ thành lưới các ô vuông đơn vị, mỗi ô vuông được ban tổ chức ghi sẵn một trong hai số 0 hoặc 1. Môi người tham gia trò chơi được ban tố chức yêu câu gâp tờ giây một lân theo đương ke ngang và mt ln theo đường kẻ dọc. Theo nêp gp đó sẽ chia t giấy thành 4 phần. Người thắng cuộc là người tìm được cách gấp tờ giấy mà phần có ít số 1 nhất (trong 4 phần của tờ giấy sau khi gấp) là nhiều nhất so với các cách gấp khác.

Yêu cầu: Bạn hãy tìm một cách gấp giấy thỏa mãn yêu cầu của ban tổ chức sao cho bạn là người thắng cuộc.

Dữ liệu vào: Cho từ tệp văn bản GAPGIAY.INP có dạng:

• Dòng thứ nhất ghi số nguyên dương n (2 ≤ n ≤ 250)

• Tiêp theo là n dòng, mỗi dòng ghi n số: số 0 hoặc số 1, tương ứng với các sô được ghi trên tờ giấy.

Các sô ghi trên cùng một dòng cách nhau một kí tự trăng.

Kết quả: Ghi vào tệp văn bản GAPGIAY.OUT gồm một dòng ghi một số nguyên là số lượng số 1 trên phần giấy có ít số 1 nhất của cách gấp tìm được.

Ví dụ:

Input:

6
1 0 1 0 0 1
0 1 0 0 0 1
1 0 0 0 0 0
0 1 1 0 0 1
0 1 0 0 1 0
1 0 1 0 0 0

Output:

3

Minh họa:

Ràng buộc dữ liệu:

• Có 70% số test tương ứng 70% số điểm có 2 ≤ n ≤ 150

• Có 30% số test tương ứng 30% số điểm có 150 < n ≤ 250