Minimum Coin Cost for Card Rearrangement

In the game "Hearth Collection", cards are arranged in an \(N \times N\) matrix. After an intense battle, Little Z wants to reassemble his team by reordering the cards. However, to preserve game balance, each card (of the same type) appears at most twice and the operations are limited as follows:

• You are allowed to perform horizontal swaps (i.e. swapping any two cards in the same row) an arbitrary number of times in one continuous move by paying \(A\) coins once. (Further horizontal swaps without changing to vertical swaps do not cost extra.)
• You are allowed to perform vertical swaps (i.e. swapping any two cards in the same column) an arbitrary number of times in one continuous move by paying \(B\) coins once.

However, whenever you change the swap type (from horizontal to vertical or vice versa) you must pay the corresponding coin cost again. For example, a sequence such as "horizontal swap - horizontal swap - vertical swap - vertical swap - vertical swap - horizontal swap - vertical swap" will cost \(2A+2B\) coins in total.

You are given the current configuration and the target configuration. Determine the minimum number of coins required to transform the current arrangement into the target arrangement.

Operation details:

Each horizontal operation allows any permutation of the elements in that row (but cannot affect other rows), and each vertical operation allows any permutation of the elements in that column (but cannot affect other columns). Note that:

• If the cards in every row (considered as a multiset) of the current configuration match those of the target configuration, they can be rearranged by only horizontal swaps (cost = \(A\)).
• If the cards in every column of the current configuration match those of the target configuration, they can be rearranged by only vertical swaps (cost = \(B\)).
• If the current configuration is already identical to the target, no coins are needed.

If neither of the above conditions is satisfied, then both types of operations are needed and the minimum cost will be \(A+B\). (In the rare case that both horizontal only and vertical only operations are possible, choose the cheaper option, i.e. \(\min(A, B)\)).

It is guaranteed that both configurations have the same multiset of cards overall (the special restriction that there are at most two copies of any card is always maintained). You need to compute the minimum coin cost to achieve the target configuration using the allowed operations.

inputFormat

The first line contains three integers \(N\), \(A\), and \(B\) where \(1 \leq N \leq 1000\) and \(A, B\) are positive integers representing the matrix size and the coin cost for horizontal and vertical swaps respectively.

The next \(N\) lines each contain \(N\) integers representing the current configuration.

The following \(N\) lines each contain \(N\) integers representing the target configuration.

outputFormat

Output a single integer, which is the minimum coin cost required to transform the current configuration into the target configuration.

sample

2 5 6
1 2
3 4
1 2
3 4

0