Let’s call the first operation in the problem statement as “increment/decrement” and the second operation as “swap”.

Here, let us constrain a little bit to the problem statement, so that once you performed increment/decrement, you cannot perform swap anymore.

In other words, the only procedure allowed is:

• first perform swaps any number of (possible zero) times;
• then perform increment/decrement any number of (possible zero) times.

This modification does not change the answer. Because, “swapping after incrementing/decrementing” can be replaced with “incrementing/decrementing after swapping.”

From the initial state \(A = (A_1, A_2, \ldots, A_N)\), consider the state after “swap any number of times” step is finished, where \(A\) can be expressed as \(A = (A_{P_1}, A_{P_2}, \ldots, A_{P_N})\). Here, \(P = (P_1, P_2, \ldots, P_N)\) is a permutation of \(1, 2, 3, \ldots, N\) .

What is the total cost required to make \(A\) equal to \(B\)?

• First, in the “swap any number of times” step, modifying \(A = (A_1, A_2, \ldots, A_N)\) to \(A = (A_{P_1}, A_{P_2}, \ldots, A_{P_N})\) requires \(\mathrm{inv}(P)\) number of swaps, where \(\mathrm{inv}(P)\) is the inversion number of \(P\). It requires \(\mathrm{inv}(P) \cdot Y\) yen.

• Next, in the “increment/decrement any number of times” step, making \(A = (A_{P_1}, A_{P_2}, \ldots, A_{P_N})\) equal to \(B\) requires \(\displaystyle\sum_{i = 1}^N |A_{P_i} - B_i|\) number of increments/decrements (where \(|\cdot|\) denotes the absolute value). This requires \(\displaystyle\sum_{i = 1}^N |A_{P_i} - B_i| \cdot X\) yen.

Therefore,

\(\mathrm{cost}(P) = \displaystyle\sum_{i = 1}^N |A_{P_i} - B_i|\cdot X + \mathrm{inv}(P)\cdot Y\).

Thus, this problem is boiled down to “the optimization problem to minimize \(\mathrm{cost}(P)\) by choosing appropriate \(P\).”

Here,

\(\mathrm{cost}(P)\)

\(=\displaystyle\sum_{i = 1}^N |A_{P_i} - B_i|\cdot X + \mathrm{inv}(P)\cdot Y\)

\(= \displaystyle\sum_{i = 1}^N |A_{P_i} - B_i| \cdot X + \Big( \displaystyle\sum_{i=1}^N \#\lbrace j : j > i, P_j < P_i \rbrace \Big) \cdot Y\)

\(= \displaystyle\sum_{i = 1}^N (|A_{P_i} - B_i| \cdot X + \#\lbrace j : j > i, P_j < P_i \rbrace \cdot Y)\)

\(= \displaystyle\sum_{i = 1}^N (|A_{P_i} - B_i| \cdot X + \#\lbrace p : p \in \mathcal{N} \setminus \lbrace P_1, P_2, \ldots, P_{i-1}\rbrace, p < P_i \rbrace \cdot Y)\)

where \(\#\) denotes the number of elements and \(\mathcal{N} := \lbrace 1, 2, \ldots, N\rbrace\).

Here, note that \( \#\lbrace p : p \in \mathcal{N} \setminus \lbrace P_1, P_2, \ldots, P_{i-1}\rbrace, p < P_i \rbrace\) depends only on \(\lbrace P_1, P_2, \ldots, P_{i-1} \rbrace\) and \(P_i\) (but not on the actual permutation \(P_1, P_2, \ldots, P_{i-1}\)).
Thus, for \(S \subseteq \mathcal{N}\) and \(x \in \mathcal{N} \setminus S\), defining

\(f(S, x) := \#\lbrace p : p \in \mathcal{N} \setminus S, p < x \rbrace\),

then

\(\mathrm{cost}(P) = \displaystyle\sum_{i = 1}^N (|A_{P_i} - B_i| \cdot X + f(\lbrace P_1, P_2, \ldots, P_{i-1} \rbrace, P_i) \cdot Y).\)

Therefore, the original problem can be rephrased as follows.

You will determine the element of \(P\) in the order of \(P_1, P_2, \ldots, P_N\). When the first \((i-1)\) elements \(P_1, P_2, \ldots, P_{i-1}\) is already determined, choosing \(x\) as the next element \(P_i\) costs

\(|A_{x} - B_i| \cdot X + f(\lbrace P_1, P_2, \ldots, P_{i-1} \rbrace, x) \cdot Y.\)

Find the minimum total cost to determine all the elements of \(P\).

We will solve this problem by Dynamic Programming (DP).

When the first \(i\) elements of \(P\), which are \(P_1, P_2, \ldots, P_i\), is already determined, and \(S = \lbrace P_1, P_2, \ldots, P_i \rbrace\), then let’s call this state \(S\).

When no element of \(P\) is determined, the state is \(\emptyset\). Every time an element of \(P\) is determined, the current state changes, reaching state \(\mathcal{N}\) after all the elements of \(P\) is determined.

For \(S \subseteq \mathcal{N}\), define \(\mathrm{dp}[S]\) as follows.

\(\mathrm{dp}[S] := \) (Minimum total cost required to reach state \(S\))

The answer for the original problem is the minimum total cost to reach state \(\mathcal{N}\), that is, \(\mathrm{dp}[\mathcal{N}]\).:

First, consider the initialization of DP. By the definition of \(\mathrm{dp}[\ast]\),

\(\mathrm{dp}[\emptyset] = 0\).

Also, for convenience, for \(S \neq \emptyset\) we initialize as

\(\mathrm{dp}[S] \leftarrow \infty\).

Next, consider the transitions of DP.

When the current state is state \(S\), we can choose as the next element \(P_{\#S+1}\) any elements of \(\mathcal{N} \setminus S\). Choosing \(P_{\#S+1} = x \in \mathcal{N} \setminus S\) requires \( |A_{x} - B_{\#S+1}| \cdot X + f(S, x) \cdot Y\) cost, changing the current state to state \(S \cup \lbrace x \rbrace\).

Correspondingly, for each \(x \in \mathcal{N} \setminus S\), we have the following transition:

\(\mathrm{dp}[S \cup \lbrace x\rbrace] \leftarrow \min( \mathrm{dp}[S \cup \lbrace x\rbrace], \mathrm{dp}[S] + |A_{x} - B_{\#S+1}| \cdot X + f(S, x) \cdot Y)\)

By computing \(\mathrm{dp}[\ast]\) by the aforementioned initialization and transition, the answer for this problem is obtained as \(\mathrm{dp}[\mathcal{N}]\).

Therefore, this problem can been solved in a total of \(\mathrm{O}(N^2\cdot 2^N)\) time (or \(\mathrm{O}(N\cdot 2^N)\) time depending on implementation).

We will show a sample code in C++ below.

#include <iostream>
#include <vector>
#include <algorithm>
#define inf 1e18
using namespace std;
typedef long long ll;

ll N, X, Y;
ll A[20], B[20];
ll dp[1<<18];

int f(int S, int x)
{
  int ret = 0;
  for(int p = 1; p <= N; p++){
    if((S & (1<<(p-1))) == 0 && p < x) ret++;
  }
  return ret;
}

int main(void)
{
  cin >> N >> X >> Y;
  for(int i = 1; i <= N; i++) cin >> A[i];
  for(int i = 1; i <= N; i++) cin >> B[i];

  dp[0] = 0;
  for(int S = 1; S < (1<<N); S++) dp[S] = inf;

  for(int S = 0; S < (1<<N); S++){
    int sizeS = 0;
    for(int i = 1; i <= N; i++) if(S & (1<<(i-1))) sizeS++;
    for(int x = 1; x <= N; x++){
      if(S & (1<<(x-1))) continue;
      dp[S|(1<<(x-1))] = min(dp[S|(1<<(x-1))], dp[S] + abs(A[x] - B[sizeS+1]) * X + f(S, x) * Y);
    }
  }
  cout << dp[(1<<N)-1] << endl;

  return 0;
}