New Year is coming, and Jaehyun decided to read many books during 2015, unlike this year. He has n books numbered by integers from 1 to n. The weight of the i-th (1 ≤ i ≤ n) book is w_{i}.

As Jaehyun's house is not large enough to have a bookshelf, he keeps the n books by stacking them vertically. When he wants to read a certain book x, he follows the steps described below.  He lifts all the books above book x.  He pushes book x out of the stack.  He puts down the lifted books without changing their order.  After reading book x, he puts book x on the top of the stack. 

[Image] 

He decided to read books for m days. In the j-th (1 ≤ j ≤ m) day, he will read the book that is numbered with integer b_{j} (1 ≤ b_{j} ≤ n). To read the book, he has to use the process described in the paragraph above. It is possible that he decides to re-read the same book several times.

After making this plan, he realized that the total weight of books he should lift during m days would be too heavy. So, he decided to change the order of the stacked books before the New Year comes, and minimize the total weight. You may assume that books can be stacked in any possible order. Note that book that he is going to read on certain step isn't considered as lifted on that step. Can you help him?


-----Input-----

The first line contains two space-separated integers n (2 ≤ n ≤ 500) and m (1 ≤ m ≤ 1000) — the number of books, and the number of days for which Jaehyun would read books.

The second line contains n space-separated integers w_1, w_2, ..., w_{n} (1 ≤ w_{i} ≤ 100) — the weight of each book.

The third line contains m space separated integers b_1, b_2, ..., b_{m} (1 ≤ b_{j} ≤ n) — the order of books that he would read. Note that he can read the same book more than once.


-----Output-----

Print the minimum total weight of books he should lift, which can be achieved by rearranging the order of stacked books.


-----Examples-----
Input
3 5
1 2 3
1 3 2 3 1

Output
12



-----Note-----

Here's a picture depicting the example. Each vertical column presents the stacked books. [Image]

Difficulty: interview

Starter code:

Solutions:
line = input().split()
n = int(line[0])
m = int(line[1])

W = [int(w) for w in input().split()]
B = [int(b) for b in input().split()]

ans = 0
lst = [0 for i in range(n)]
for i in range(m):
    arr = list(lst)
    for j in range(i):
        if B[i - j - 1] == B[i]:
            break
        arr[B[i - j - 1] - 1] = 1
    for i in range(n):
        if arr[i] == 1:
            ans += W[i]
print(ans)
            


"""
Codeforces Contest Good Bye 2014 Contest Problem C

Author  : chaotic_iak
Language: Python 3.4.2
"""

################################################### SOLUTION

def main():
    n,m = read()
    w = read()
    b = read()
    bookset = set(range(1,n+1))
    print(solve(b, w, bookset, n))

def solve(b, w, bookset, n):
    if len(b) <= 1: return 0
    used = [0] * (n+1)
    sm = 0
    for i in range(len(b)):
        if not used[b[i]]:
            sm += 1
        if sm == len(bookset):
            res = solve(b[:i], w, bookset - {b[i]}, n)
            for j in range(i, len(b)):
                for k in range(n+1):
                    if used[k] > used[b[j]]: res += w[k-1]
                used[b[j]] = j+1
            return res
        used[b[i]] = i+1
    bookset = set(filter(lambda x: x, used))
    return solve(b, w, bookset, n)

#################################################### HELPERS



def read(mode=2):
    # 0: String
    # 1: List of strings
    # 2: List of integers
    inputs = input().strip()
    if mode == 0: return inputs
    if mode == 1: return inputs.split()
    if mode == 2: return list(map(int, inputs.split()))

def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")

write(main())

import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
w = [int(i) for i in input().split()]
arr = [(int(i) - 1) for i in input().split()]
v = []
s = 0
used = [False] * n
for i in range(m):
    if not used[arr[i]]:
        used[arr[i]] = True
        v.append(arr[i])
for i in range(m):
    j = 0
    while v[j] != arr[i]:
        s += w[v[j]]
        j += 1
    #print(v)
    v = [v[j]] + v[0:j] + v[j + 1:]
print(s)

n,m = list(map(int,input().split()))
w = list(map(int,input().split()))
b = list(map(int,input().split()))
when = []

j = n+m
for i in range(n):
    try:
        j = b.index(i+1)
    except:
        pass
    if j != n+m:
        when.append([j,i])
    j = n+m

when = list(sorted(when))
stack = []
for i in range(len(when)):
    stack.append(when[i][1])

count = 0
where = n+m
for i in range(m):
    where = stack.index(b[i]-1)
    for j in range(where):
        count += w[stack[j]]
    stack = [stack[where]]+stack[:where]+stack[where+1:]

print(count)


import sys

def main():
    n,m = tuple([int(x) for x in input().split()])
    w = [int(x) for x in input().split()]
    b = [int(x) - 1 for x in input().split()]
    o = []
    for i in range(m):
        if len(o) == n:
            break
        if b[i] not in [x[0] for x in o]:
            o.append((b[i],w[b[i]]))
    s = 0
    for i in range(m):
        ind = [o[i][0] for i in range(len(o))].index(b[i]) 
        s += sum([o[i][1] for i in range(ind)])
        el = o.pop(ind)
        o.insert(0,el)
    print(s)

def __starting_point():
    main()

__starting_point()

n, m = list(map(int, input().split()))
w = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = list()
used = [False] * (n + 1)
for i in range(len(b)):
    if not used[b[i]]:
        ans.append(b[i])
        used[b[i]] = True
anss = 0
for i in range(len(b)):
    top = -1
    for j in range(len(ans)):
        if ans[j] == b[i]:
            top = ans[j]
            
            for k in range(j, 0, -1):
                ans[k] = ans[k - 1]
                anss += w[ans[k - 1] - 1]
            break
    ans[0] = top
print(anss)


from collections import deque

def intput():
    return [int(x) for x in input().split(" ")]


def main(ws, ords):
    stack = []
    seen = set()
    for o in ords:
        if o not in seen:
            stack.append(o)
            seen.add(o)
        if len(stack) == len(ws):
            break

    s = 0
    for o in ords:
        idx = stack.index(o)
        # print(stack, o, idx)
        w = [ws[b - 1] for b in stack[:idx]]
        # print(w)
        s += sum(w)
        stack.insert(0, stack.pop(idx))

    print(s)

def parse():
    _ = intput()
    ws = intput()
    ords = intput()
    # print(ws, ords)
    return ws, ords

main(*parse())


from itertools import permutations as perm


def weigh(seq, order_seq):
    ret = 0
    w_seq = list(seq[:])
    for idx,i in enumerate(order_seq):
        for book_idx in w_seq[:w_seq.index(i)]:
            # print(book_idx)
            ret += weights[book_idx-1]
        w_seq.insert(0, w_seq.pop(w_seq.index(i)))
    return ret

n, m = tuple(map(int, input().split(' ')))
weights = tuple(map(int, input().split(' ')))
order = tuple(map(int, input().split(' ')))

already = []
for i in order:
    if i not in already:
        already.append(i)
print(weigh(already, order))


# min_ret = 100001
# for p in perm([x for x in range(1,n+1)]):
#     # print(p)
#     w = weigh(p, order)
#     if w < min_ret:
#         min_ret = w
# print(min_ret)


__author__ = 'Rakshak.R.Hegde'
"""
Created on Dec 30 2014 PM 09:40

@author: Rakshak.R.Hegde
"""

from collections import deque
from bisect import bisect


def mint(): return map(int, input().split())


n, m = mint()
w = tuple(mint())
b = mint()
stack = []
lifts = 0
for x in b:
    for i, v in enumerate(stack):
        if v == x:
            stack.pop(i)
            break
    else:
        i = 0
    # print('i:{}; stack:{}'.format(i, stack))
    for i in range(i, len(stack)):
        lifts += w[stack[i] - 1]
    stack.append(x)
print(lifts)

a, b = list(map(int, input().split(' ')))
c = list(map(int, input().split(' ')))
d = list(map(int, input().split(' ')))
e = []
dictx = {}
for i in range(1, a+1):
    dictx[i] = c[i-1]
for i in d:
    if i not in e:
        e.append(i)

tot = 0
for i in d:
    indx = e.index(i)
    tot += sum([dictx[i] for i in e[:indx]])
    e = [e[indx]] + e[:indx] + e[indx+1:]
print(tot)


n,m=map(int,input().split())
w=list(map(int,input().split()))
b=list(map(int,input().split()))
A=0
for i in range(m):
 d,j={},i-1
 while j>=0 and b[j]!=b[i]:
  if (d.get(b[j],1)):
   A+=w[b[j]-1]
   d[b[j]]=0
  j-=1
print(A)

#!/usr/bin/env python3

n, m = list(map(int, input().split()))
w = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = 0
for i in range(m):
    flag = dict()
    for j in range(i-1, -1, -1):
        if b[j] == b[i]:
            break
        if flag.get(b[j], True):
            ans += w[b[j] - 1]
            flag[b[j]] = False

print(ans)


input()
w = list(map(int, input().split()))
b = list(map(int, input().split()))
a = []
ans = 0
for x in b:
    x -= 1
    cur_sum = 0
    for i, num in enumerate(a):
        if num == x:
            a = [num] + a[:i] + a[i + 1:]
            break
        cur_sum += w[num]
    else:
        a = [x] + a
    ans += cur_sum
print(ans)

def ans():
    n, m= [int(i) for i in input().split()]
    w= [int(i) for i in input().split()]
    b= [int(i) for i in input().split()]
    
    books= []
    for i in b:
        if i not in books:
            books.append(i)
    
    #print(books, w)
    ans= 0        
    for i in b:
        arr= books[:books.index(i)]
        #print(i, arr, "h")
        for j in arr:
            ans+= w[j-1]
            #print(i, j, w[i-1], ans)
        
        books.remove(i)
        books.insert(0, i)
    
    print(ans)
    return

ans()

input()
w = list(map(int, input().split()))
b = list(map(int, input().split()))
a = []
ans = 0
for x in b:
    x -= 1
    cur_sum = 0
    for i, num in enumerate(a):
        if num == x:
            a = [num] + a[:i] + a[i + 1:]
            break
        cur_sum += w[num]
    else:
        a = [x] + a
    ans += cur_sum
print(ans) 

n, m = [int(x) for x in input().split()]
w = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
ans = 0
state = [0] * n
used = [0] * n
ptr = 0
for i in b:
	if not used[i - 1]:
		used[i - 1] = 1
		state[ptr] = (i, w[i - 1])
		ptr += 1
for i in b:
	ind = state.index((i, w[i - 1]))
	ans += sum(x[1] for x in state[: ind])
	state = [state[ind]] + state[: ind] + state[ind + 1: ]
print(ans)


N_M=list(map(int,input().split()))
Weights=list(map(int,input().split()))
Good_Books=list(map(int,input().split()))
Times=[]
Count=sum(N_M)
for I in range(N_M[0]):
    try:
        Count=Good_Books.index(I+1)
    except ValueError:
        pass
    if not Count==sum(N_M):
        Times.append([Count,I])
    Count=sum(N_M)
Times.sort()
Times=list(Times)
Heap=[]
for I in range(len(Times)):
    Heap.append(Times[I][1])
Count=0
Positions=sum(N_M)
for I in range(N_M[1]):
    Positions=Heap.index(Good_Books[I]-1)
    for I_2 in range(Positions):
        Count+=Weights[Heap[I_2]]
    Heap=[Heap[Positions]]+Heap[:Positions]+Heap[Positions+1:]
print(Count)


#!/usr/bin/env python3

n, m = (int(x) for x in input().split())
w = [int(x) for x in input().split()]  # len(w) == n
b = [int(x) - 1 for x in input().split()]  # len(b) == m

visited = [False] * n
stack = []
for book in b:
    if not visited[book]:
        stack.append(book)
        visited[book] = True
stack.reverse()

total_weight = 0
for reading in b:
    p = len(stack) - 1
    while stack[p] != reading:
        total_weight += w[stack[p]]
        p -= 1
    else:
        stack.__delitem__(p)
        stack.append(reading)

print(total_weight)

def main():
    input()
    ww = list(map(int, input().split()))
    bb = [int(_) - 1 for _ in input().split()]
    aa = []
    for i in bb:
        if i not in aa:
            aa.append(i)
    aa.reverse()
    tot = 0
    for b in bb:
        idx = aa.index(b)
        del aa[idx]
        tot += sum([ww[_] for _ in aa[idx:]])
        aa.append(b)
    print(tot)


def __starting_point():
    main()

__starting_point()

n, m = map(int,input().split())
w = [int(x) for x in input().split()]
b = [(int(x)-1) for x in input().split()]
w  += [0]
a = 0
for i in range(m):
    for j in range(i-1,-1,-1):
        if b[j] == b[i]:
            b[j] = n
            break
        a += w[b[j]]
print(a)

n, m = map(int, input().split())
w = [0] + list(map(int, input().split()))
t, p = [], [0] * (n + 1)
s = 0
for i in map(int, input().split()):
    if p[i]:
        k = t.index(i)
        s += sum(w[j] for j in t[k + 1: ])
        t.append(t.pop(k))
    else:
        s += sum(w[j] for j in t)
        t.append(i)
        p[i] = 1
print(s)

# coding: utf-8
n, m = [int(i) for i in input().split()]
w = [0]+[int(i) for i in input().split()]
b = [int(i) for i in input().split()]
books = []
for book in b:
    if book not in books:
        books.append(book)
books.reverse()
ans = 0
for book in b:
    index = books.index(book)
    ans += sum([w[i] for i in books[index+1:]])
    del(books[index])
    books.append(book)
print(ans)


books,reads=list(map(int,input().split()))

booksw=list(map(int,input().split()))

readl=list(map(int,input().split()))

res=[]

for b in readl:
    if(b not  in res):
        res.append(b)
sum=0
for l in readl:
    for b in res:
        if(b==l):
            res.remove(b)
            poped=b
            break
        sum=sum+booksw[b-1]
    res=[poped]+res

print(sum)


def f(s):
    return int(s) - 1

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(f, input().split()))
c = [[0] * n for i in range(n)]
o = 0
for i in range(m):
    for j in range(n):
        if j != b[i]:
            c[j][b[i]] = 1
    for j in range(n):
        if c[b[i]][j] == 1:
            o += a[j]
        c[b[i]][j] = 0
print(o)

n,m=list(map(int,input().split()))
w=list(map(int,input().split()))
l=list(map(int,input().split()))
k=0
f=[]
for x in l :
    x-=1
    if x not in f :
        for y in f :
            k+=w[y]
        f=[x]+f
    else :
        for i in range(len(f)) :
            if f[i]!=x :
                k+=w[f[i]]
            else :
                break
        del(f[i])
        f=[x]+f
print(k)