問題文

長さ $N$ の整数列 $A$、長さ $M$ の整数列 $B, C$ が与えられます。

また、空の列 $S$ があり、あなたは以下の操作を列の長さが $M$ になるまで行うことができます。

• 操作前の列 $S$ の長さを $l$ とする。$1 \leq k \leq \min(M - l, N)$ を満たす整数 $k$ を選び、連続部分列 $(A_1, A_2, …, A_k)$ を列 $S$ の末尾に追加する。
このとき、コストが $k \times C_l$ だけかかる。

操作後に列 $S$ を列 $B$ に一致させることができるかどうかを判定し、できる場合は最小のコストを求めてください。

制約

• $1 \leq N, M \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• $1 \leq C_i \leq 10^9$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$
$A_1$ $A_2$ ... $A_N$ 
$B_1$ $B_2$ ... $B_M$ 
$C_0$ $C_1$ ... $C_{M - 1}$  

出力

列 $S$ を列 $B$ に一致させるための最小のコストを一行に出力せよ。

一致させられない場合には $-1$ を出力せよ。

サンプル

4 7
1 2 3 1
1 1 2 3 1 1 2
1 2 3 2 1 2 3

12

3 4
1 3 2
1 3 1 2
1 1 1 1

-1