今，G○○gle Code Jam の地区大会が始まろうとしている． 斜め右前の席に座っている男の ID は lyrically と言うらしい． 東京大学時代の記憶に，似たような ID の仲間が居た覚えがあるが，僕の仲間は一人残さず美少女だったはずだ．
僕の記憶の中の lyrically は，アルゴリズムの力や実装の力もさながら， 気合で問題に正解することにも定評があった． 例えば，計算量が多少悪いプログラムでも，上手な実装をすることで高速にし， 正解とするようなことも得意としていた．
プログラムを高速にする上で，非常に大切になってくるのが， キャッシュメモリとの親和性である．
ブロック毎に読み込みのコストが異なるメモリを考える． 起こる全てのメモリアクセスがあらかじめ分かった状態での， フルアソシアティブのキャッシュメモリでの最善なキャッシュ戦略を求めたい． 以下，平易な言葉で説明する．
M 個の箱と，N 個のボールがある． ボールには 1 から N までの番号が付いており， 各ボール i には重さ wi が決まっている． また，長さ K の数列 a1, a2, …, aK が与えられる． 各 aj は 1 ≤ aj ≤ N を満たす整数である．
はじめは全ての箱は空である． j = 1, 2, …, K の順に，以下を行いたい．
コストの和の最小値を計算するプログラムを作成せよ．
入力の最初の行は 3 つの整数 M, N, K を含む．
続く N 行の i 行目には整数 wi が書かれている．
続く K 行の j 行目には整数 aj が書かれている．
コストの和の最小値を出力せよ．
この問題の判定には，20 点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は以下を満たす．
入力例 1:
3 3 6 10 20 30 1 2 3 1 2 3
入力例 1 に対する出力例:
60
入力例 2:
2 3 6 10 20 30 1 2 3 1 2 3
入力例 2 に対する出力例:
80