個の卵が横一列に並んでいます。
卵には、色 から までのいずれかの色で塗られており、左から 個目の卵は、色 で塗られています。
また、何回でも好きな卵を選んで色を塗り変えることができ、卵を色 に塗り変えるには、 の費用がかかります。
いずれかの連続した 個の卵の色を全て同じにするためにかかる費用の最小値を求めてください。
入力は以下の形式で標準入力から与えられる。
N M K C1 C2 …… CN A1 A2 …… AM
問題の答えを出力せよ。
5 3 3 1 2 1 3 2 10 10 10
10
番目の卵を色 に塗り替えると、 番目から 番目の卵の色が同じになり、目標を達成できます。
かかる費用は で、これより費用を少なくすることはできません。
5 3 3 1 1 1 1 1 10 10 10
0
最初から目標が達成されている場合もあります。