现在,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 的顺序,想进行以下操作。 如果有
- 球 aj 放入的箱子,则不进行任何操作。
- 这项操作的成本为 0。 如果没有
- 球 aj 放入的箱子,则将球放入任意一个箱子 aj 。
- 把球放进盒子时,如果盒子里已经有球,就把它带到外面。
- 这次手术的费用是 waj (费用不取决于你放入的盒子或取出的球。)
创建一个程序来计算最小成本总额。
入力
输入的第一行包含三个整数。 M, N, K 。
继续 N 线 i 行是一个整数 wi 被写下了。
继续 K 线 j 行是一个整数 aj 被写下了。
出力
输出成本的最低总和。
制約
- 1 ≤ M ≤ 10
- 1 ≤ N ≤ 104
- 1 ≤ K ≤ 104
- 1 ≤ wi ≤ 104
- 1 ≤ aj ≤ N
部分点
针对该问题的判断设置了一组20分的测试用例。 该组中包含的测试用例的输入满足以下条件。
- 1 ≤ M ≤ 3
- 1 ≤ N ≤ 10
- 1 ≤ K ≤ 103
入出力例
入力例 1
入力例 1:
3 3 6 10 20 30 1 2 3 1 2 3
输入示例 1 的输出示例:
60
入力例 2
入力例 2:
2 3 6 10 20 30 1 2 3 1 2 3
输入示例 2 的输出示例:
80