Gerrymandering 2

Time limit1sMemory limit512 MB

Summary
For an N x N grid, try every valid 5-way district split defined by a reference point and two boundary lengths, and report the smallest difference between the largest and smallest district populations.
Level

Medium6 of 10

Topics
Brute force, Simulation, Implementation, Prefix sum
Solved
No attempts yet

Problem

Gujehyeon, the mayor of Jaehyeon City, has spent the past few years gerrymandering districts to favor his own party. With no power left to check him, he exercised his authority very unfairly, and even renamed the city to Jaehyeon City. For this election, he wants to draw the districts as fairly as possible.

Jaehyeon City can be represented as an N×N grid. Each cell is a district, and the district in row r, column c is written (r, c). The districts must be divided into five electoral districts, and each district must belong to one of the five. An electoral district must contain at least one district, and all districts that belong to one electoral district must be connected. Two districts A and B are connected when you can travel from A to B through adjacent districts. The intermediate adjacent districts number zero or more, and all of them must belong to the same electoral district.

The method of dividing the electoral districts is as follows.

  1. Choose a reference point (x, y) and the boundary lengths d1 and d2. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)

  2. The following cells are boundary lines.

    • Boundary line 1: (x, y), (x+1, y-1), ..., (x+d1, y-d1)
    • Boundary line 2: (x, y), (x+1, y+1), ..., (x+d2, y+d2)
    • Boundary line 3: (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
    • Boundary line 4: (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

  3. The cells on the boundary lines and inside them form electoral district 5.

  4. For a district (r, c) not included in electoral district 5, its electoral district number follows these rules.

    • Electoral district 1: 1 ≤ r < x+d1, 1 ≤ c ≤ y, upper left of boundary line 1
    • Electoral district 2: 1 ≤ r ≤ x+d2, y < c ≤ N, upper right of boundary line 2
    • Electoral district 3: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2, lower left of boundary line 3
    • Electoral district 4: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N, lower right of boundary line 4

Below are examples of dividing a 7×7 Jaehyeon City into five electoral districts.

x = 2, y = 4, d1 = 2, d2 = 2x = 2, y = 5, d1 = 3, d2 = 2x = 4, y = 3, d1 = 1, d2 = 1

The population of district (r, c) is A[r][c], and the population of an electoral district is the sum of the populations of the districts it contains. Among all ways of dividing the electoral districts, find the minimum of the difference in population between the most populous electoral district and the least populous electoral district.

Input

The first line gives the size N of Jaehyeon City.

From the second line, N lines each give N integers. The integer in row r, column c is A[r][c].

Output

Print on the first line the minimum of the difference in population between the most populous electoral district and the least populous electoral district.

Constraints

  • 5 ≤ N ≤ 20
  • 1 ≤ A[r][c] ≤ 100

Examples3

  1. Example 1

    Input
    6
1 2 3 4 1 6
7 8 9 1 4 2
2 3 4 1 1 3
6 6 6 6 9 4
9 1 9 1 9 5
1 1 1 1 9 9
    Expected output
    18

  2. Example 2

    Input
    6
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
    Expected output
    20

  3. Example 3

    Input
    8
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 1
4 5 6 7 8 9 1 2
5 6 7 8 9 1 2 3
6 7 8 9 1 2 3 4
7 8 9 1 2 3 4 5
8 9 1 2 3 4 5 6
    Expected output
    23