Description

In the XX game, the player can edit the land in the game directly by using the land editing functionality. In this game, the land consists of cube block with size of 1 x 1 x 1. At this point, the block cannot float in the air or be placed across several spaces. Hence, the player should edit the land by adding a block to the top of space or removing the uppermost block. At this point, since adding or removing a block consumes a game money, the player should carefully determine the number of blocks to add or remove.

A player who enjoys this game wants to build own villa on the "N" x "N" region. To this end, the height of all spaces on this region should be the same. At this point, adding and removing a block requires cost of "P" and "Q", respectively.
The following shows an example of making the height of all spaces on 3 x 3 regions as the same when adding and removing a block consumes cost of 5 and 3, respectively.

예시1_ciodtv.png

When blocks are places as shown in the above figure, the result of making the height of all spaces as 3 is as follows.

예시3_irfpxy.png

To this end, the player should remove 2 blocks higher than height 3 and add 8 blocks at the space lower than height 3. The total cost is 2 x 3 + 8 x 5 = 46.

But, to make the height of all spaces as 2, the player should remove 6 blocks and add 3 blocks, consuming cost of 6 x 3 + 3 x 5 = 33. This is the minimum cost.

예시2_xv5wiz.png

Given an array land representing the current status of land and the cost for adding a block P, and the cost for removing a block Q as parameters, write a function "solution" to return the minimum cost required to make the height of all spaces as the same.

Constraints
  • land is 2-dimensional array with size of "N" x "N". The range of "N" is 1 ≤ N ≤ 300.
  • Each element of "land" indicates the number of blocks at each space, and integer number between 0 and 1,000,000,000.
  • Adding a block requires cost of P and removing a block requires cost of Q. They are natural number with range of 1 ≤ P, Q ≤ 100.

Examples
land P Q result
[[1, 2], [2, 3]] 3 2 5
[[4, 4, 3], [3, 2, 2], [ 2, 1, 0 ]] 5 3 33

Example #1

  • To make the height of all spaces as 1, the player should remove 4 blocks, consuming cost of 8.
  • To make the height of all spaces as 2, the player should add 1 block and remove 1 block, consuming cost of 5.
  • To make the height of all spaces as 3, the player should add 4 blocks, consuming cost of 12.

Hence, return 5 because the minimum cost is 5.

Example #2
It is the same with an example in the problem statement, and the minimum cost if 33.

Result Stop
Result of [Run] or [Submit] will be displayed here