Description

Xiao Z has recently become addicted to a game called Hearthstone Collection. In the game, you need to use cards arranged in an $N \times N$ matrix to defeat your enemies.

In this game, formation is important; for example, "Sunfury Protector" and "Ancient Watcher" placed together can have a better effect. For balance, at most $2$ cards of the same kind may be deployed.

After a fierce battle, Xiao Z wants to rearrange his lineup. In the game, Xiao Z can pay $A$ coins to perform arbitrary horizontal swaps, and pay $B$ coins to perform arbitrary vertical swaps.

You only need to pay once to make any number of swaps of one type, until you stop and perform the other type of swaps, at which point you need to pay the fee for the other type. For example, "horizontal swap - horizontal swap - vertical swap - vertical swap - vertical swap - horizontal swap - vertical swap" costs $2A + 2B$ coins in total.

Xiao Z wants to know the minimum number of coins he needs to transform his current arrangement into his desired arrangement.

Input Format

The first line contains three integers $N, A, B$, representing the size of the matrix, the cost of a horizontal swap, and the cost of a vertical swap.

The next $N$ lines each contain $N$ integers, representing the card type at each position in the matrix before swapping.

The next $N$ lines each contain $N$ integers, representing the target matrix.

Output Format

Output the minimum number of coins required to transform the current arrangement into the desired arrangement. If it is impossible, output Fail.

3 16 9
2 5 6
1 1 3
7 8 3
2 5 1
3 3 6
7 8 1

34

2 193 43
1 2
2 1
1 2
2 3

Fail

3 10 20
1 2 3
4 5 4
3 2 1
2 1 2
1 5 3
4 3 4

30

Hint

For $68\%$ of the testdata, the answer requires paying at most $1$ fee.

For $86\%$ of the testdata, the answer requires paying at most $2$ fees.

For $100\%$ of the testdata, $1 \leq n \leq 300,1 \leq A,B \leq 1000000,1 \leq$ card type ID $\leq 100000$.

Translated by ChatGPT 5