Problem Description

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

In this game, arranging troops is an important aspect, such as placing "Sunfury Protector" and "Ancient Watcher" together for better effects. For the balance of the game, a maximum of 2 cards of the same type can be used in battle.

After a fierce battle, Little Z wants to rearrange his team. In the game, Little Z can pay $A$ gold coins to allow you to swap cards horizontally, and pay $B$ gold coins to allow you to swap cards vertically.

You only need to pay once for a certain type of swap to perform it any number of times, until you stop and switch to another type of swap, at which point you need to pay for the other type of swap. For example, "horizontal swap-horizontal swap-vertical swap-vertical swap-vertical swap-horizontal swap-vertical swap" would cost a total of $2A + 2B$ gold coins.

Little Z wants to know the minimum amount of gold coins he needs to pay to transform his current arrangement into the desired arrangement.

Input Format

The first line contains three numbers $N, A, B$, representing the size of the matrix, the cost of horizontal swaps, and the cost of vertical swaps, respectively.

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

The next $N$ lines each contain $N$ integers, representing the type of card in each position of the target matrix.

Output Format

Output the minimum amount of gold coins needed to transform the current arrangement into the desired arrangement. If it is not possible to transform successfully, output Fail.

Sample Input and Output

Sample Input #1

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

Sample Output #1

34

Sample Input #2

2 193 43
1 2
2 1
1 2
2 3

Sample Output #2

Fail

Sample Input #3

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

Sample Output #3

30

Notes

For 68% of the data, the answer requires at most 1 payment.

For 86% of the data, the answer requires at most 2 payments.

For 100% of the data, $1 \leq N \leq 300, 1 \leq A, B \leq 1000000, 1 \leq$ card type number $\leq 100000$.

见题面 Input 部分

见题面 Output 部分