Daniyal the space lord loves the tax that he collects from his space colonies, so he decides to build a weird new colony in the shape of a 4-dimensional "cube". He can describe how big this colony is by the lengths of the four different axes of the colony. However, his citizens complain about a lack of transportation, and so Daniyal tries connecting each set of opposite sides of his city together such that the distance between each point in the colony is drastically shortened (i.e., he rolls the colony into a torus).
It's time to collect the tax! For each citizen in the colony, Daniyal gives citizen ~i~ a tax estimate ~t_i~, describing how much the citizen will pay him. To make tax collection easy, he defines a neighbourhood to be some "rectangular"-shaped non-empty set of adjacent citizens, and decides to tax only the neighbourhood with the highest collective tax estimate. To make things more "fair", the citizens in that neighbourhood will split the payment equally, with individual payments rounded down. Daniyal is lazy, so help him calculate this average tax payment.
Note: if two neighbourhoods have the same collective tax estimate, Daniyal will only tax the one that minimizes payment per citizen. It is guaranteed that this will break any tie.
The first line of input will contain four space-separated integers ~X~, ~Y~, ~Z~, and ~W~, each denoting the length of one of the axes of the colony. The next line will contain ~X \times Y \times Z \times W~ space-separated integers, where the ~i~th integer represents ~t_i~, the tax estimate for the ~i~th citizen.
The integers are presented in order from a corner of the colony to the opposite corner (i.e., the flattened 4D colony, filling up each dimension one at a time).
For all subtasks, ~-10^9 \le t_i \le 10^9 + 1~.
Subtask 1 [10%]
- ~1 \le X, Y, Z, W \le 6~
Subtask 2 [20%]
- ~1 \le X, Y, Z, W \le 10~
- ~1 \le X \times Y \times Z \times W \le 8\,000~
Subtask 3 [70%]
- ~1 \le X, Y, Z, W \le 21~
- ~1 \le X \times Y \times Z \times W \le 11\,000~
The output should contain a single integer; the rounded-down average tax payment in the highest-paying neighbourhood in the colony.
Sample Input 1
2 3 1 1 3 2 5 7 1 -15
Sample Output 1
The neighbourhood that will be taxed is that composed of citizens paying 3, 2, 5, and 7 dollars, resulting in a collective tax estimate of 17, split equally across 4 citizens. The citizen paying 1 dollar is not included in this neighbourhood, because to make the neighbourhood "rectangular"-shaped, the citizen paying -15 dollars would also have to be included, making the overall payment non-maximal.
Sample Input 2
2 2 3 2 442294612 -386253016 -505717487 122716090 -82536811 650826785 392919 269868536 -681924097 813589289 -272524140 913288054 442835178 -867109293 144211806 -250882696 -751764544 -754975539 -544290979 -159374076 -166647076 331222521 -845133014 -401480867
Note: the above input consists of only two lines.
Sample Output 2