Minimum Preparation Time for Two Handlers

Following the original order, assign each task to one of two processors; each processor remembers the type it handled last. If a task's type matches that processor's last type, it costs short[t], otherwise long[t]; a processor's first use costs long[t]. Find the minimum total cost of all tasks; the order may not change. short is not guaranteed to be ≤long.

输入格式

The first line contains n m, the second line contains n types in 1..m, the third line contains m short values, and the fourth line contains m long values. On this site 1≤n,m≤200000, 0≤short[t],long[t]≤10^9, and short>long as well as zero costs are allowed.

输出格式

Output a single integer, the answer.

样例 1

输入：

3 1
1 1 1
9
1

输出：

11

样例 2

输入：

4 2
1 2 1 2
0 0
5 7

输出：

12

样例 3

输入：

2 1
1 1
0
0

输出：

0

样例说明

The answers are 11, 12 and 0. In the first example the first two tasks each use an unused processor, and the third task must not invent a third cold-start processor.