E - All I Need are Numbers I Like
Milk
2
s
1024
MB
100
点
問題文
長さ $N$ の正整数列 $A = (A_1, A_2, \ldots, A_N)$ と $K$ 個の正整数を要素とする集合 $S = \lbrace S_1, S_2, \ldots, S_K\rbrace$ が与えられます。
あなたは以下の操作を好きな回数行うことができます。$1$ 回も操作を行わないことも可能です。
- $1 \leq l \leq r \leq N$ を満たす整数 $l,r$ と $v \in \lbrace 1, -1\rbrace$ を満たす整数 $v$ を選び、 $l \leq i \leq r$ を満たすすべての整数 $i$ について $A_i$ を $A_i+v$ に更新する。
あなたの目標は、$1 \leq i \leq N$ を満たすすべての整数 $i$ について、$A_i \in S$ が成り立つようにすることです。この目標を達成するために必要な操作回数の最小値を求めてください。
なお、有限回の操作によって目標が達成可能であることを証明できます。
制約
- $1 \leq N \leq 3000$
- $2 \leq K \leq 3000$
- $1 \leq A_i \leq 10^9$
- $1 \leq S_i \leq 10^9$
- $i \neq j$ ならば $S_i \neq S_j$
- 入力はすべて整数である
部分点
set1$(30$ 点$)$： $K=2$all$(70$ 点$)$：追加の制約はない
入力
入力は以下の形式で標準入力から与えられます。
$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$
$S_1$ $S_2$ $\ldots$ $S_K$
出力
答えを出力してください。
入力例 1
3 2
1 3 2
2 4
出力例 1
1
$l=1,r=2,v=1$ を選ぶような操作を $1$ 回行うことで $A=(2, 4, 2)$ となり、目標を達成できます。
これより少ない回数で目標を達成することはできないので、必要な操作回数の最小値は $1$ 回です。
この入力例は部分点 set1 の制約を満たします。
入力例 2
2 2
10 90
1 100
出力例 2
19
この入力例は部分点 set1 の制約を満たします。
入力例 3
10 3
1484 1005 1648 2656 3779 1681 2115 1764 2652 2352
1213 2784 1260
出力例 3
2647