Population Migration (APCS 2020-10 Intermediate)

Several cities are placed on an \(R\)-row, \(C\)-column grid. Position \((r,c)\) is a city when its cell contains a nonnegative integer representing its current population; a value of \(-1\) means that the position is not a city.

Two cities are adjacent only when their cells share an edge. Thus, only the four directions up, down, left, and right are considered; diagonal cells are not adjacent.

Migration on each day follows these rules:

1. Suppose a city has population \(p\) at the beginning of the day. Let \(q=\left\lfloor p/k\right\rfloor\).
2. The city sends \(q\) people to each adjacent city. No migration occurs toward a direction outside the grid or toward a cell containing \(-1\), and no population is deducted for that direction.
3. Every city computes its outgoing amount from its population at the beginning of that day, and all migrations happen simultaneously. People received during a day cannot migrate again until the next day.

Simulate \(m\) days and report the minimum and maximum city populations after day \(m\) has finished.

The following newly drawn diagram illustrates one day of the sample. A number beside an arrow is the number of people migrating in that direction; a crossed cell is not a city.

For example, the upper-left city begins with \(10\) people, so it sends \(\lfloor10/4\rfloor=2\) people to the right and \(2\) downward. At the same time, it receives \(\lfloor5/4\rfloor=1\) person from below. Its next-day population is therefore \(10-2-2+1=7\).

Input

The first line contains four positive integers \(R,C,k,m\).

The next \(R\) lines each contain \(C\) integers. The integer \(a_{r,c}\) in row \(r\), column \(c\) has the following meaning:

• \(a_{r,c}=-1\) means that the position is not a city.
• \(a_{r,c}\ge0\) is that city's population before migration begins on day \(1\).

Constraints

• \(1\le R,C,m\le50\)
• \(4\le k\le50\)
• \(-1\le a_{r,c}\le100\)
• The grid contains at least one city.
• All input values are integers.

Output

On the first line, print the minimum city population after \(m\) days.

On the second line, print the maximum city population after \(m\) days.

Scoring

The sample is judged but carries no points. There are exactly \(20\) scored groups, each worth \(5\) points:

• Groups \(1\)–\(4\) (\(20\) points): \(R=1\) and \(m=1\).
• Groups \(5\)–\(10\) (\(30\) points): \(R=1\).
• Groups \(11\)–\(20\) (\(50\) points): no additional constraints.

Sample Input

2 3 4 1
10 2 -1
5 -1 2

Sample Output

2
7

Sample Explanation

After one day, the four city populations are \(7,4,6,2\). Therefore, the minimum is \(2\) and the maximum is \(7\).

Source

APCS October 2020 implementation problem 2; rules based on ZeroJudge f313 “Population Migration” and Wang Yizhe's explanation. The statements and explanatory figure were newly prepared for AACPOJ.