新年即将到来,Jaehyun 决定在 2015 年读很多书,与今年不同。他有 n 本书,编号为 1 到 n 的整数。第 i (1 ≤ i ≤ n) 本书的重量为 wi。
由于Jaehyun的房子不够大,没有书架,所以他将n本书垂直堆叠起来。当他想读某本书x时,他遵循以下步骤。
1. 他举起了第 x 本书上面的所有书。
2. 他将书 x 从书架中推出。
3. 他放下举起的书,没有改变顺序。
4. 读完书 x 后,他将书 x 放在书架的顶部。
他决定读书m天。在第 j (1 ≤ j ≤ m) 天,他将阅读编号为整数 bj (1 ≤ bj ≤ n) 的书。要阅读这本书,他必须使用上一段中描述的过程。他可能决定将同一本书重读几次。
制定这个计划后,他意识到他在 m 天内要举起的书的总重量太重了。于是,他决定在过年前改变书籍的堆放顺序,尽量减少总重量。您可能会假设书籍可以按任何可能的顺序堆叠。请注意,他将在某个步骤中阅读的书不被视为在该步骤中被抬起。你能帮助他吗?
输入
第一行包含两个空格分隔的整数 n (2 ≤ n ≤ 500) 和 m (1 ≤ m ≤ 1000) — 书籍数量以及 Jaehyun 读书的天数。
第二行包含 n 个空格分隔的整数 w1, w2, ..., wn (1 ≤ wi ≤ 100) — 每本书的重量。
第三行包含 m 个空格分隔的整数 b1, b2, ..., bm (1 ≤ bj ≤ n) — 他要阅读的书籍的顺序。请注意,他可以多次阅读同一本书。
输出
打印他应该举起的书籍的最小总重量,这可以通过重新排列书籍的堆叠顺序来实现。
示例
输入 #1
3 5 1 2 3 1 3 2 3 1
输出 #1
12
注意
这是描述该示例的图片。每个垂直列都呈现堆叠的书籍。