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 wi.

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.

  1. He lifts all the books above book x.
  2. He pushes book x out of the stack.
  3. He puts down the lifted books without changing their order.
  4. After reading book x, he puts book x on the top of the stack.

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 bj (1 ≤ bj ≤ 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 w1, w2, ..., wn (1 ≤ wi ≤ 100) — the weight of each book.

The third line contains m space separated integers b1, b2, ..., bm (1 ≤ bj ≤ 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

Copy

3 5
1 2 3
1 3 2 3 1

Output

Copy

12

Note

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

 

按着看书的顺序摆放书。

这位大佬讲的很到位。https://blog.csdn.net/Tc_To_Top/article/details/43607321

自己看后的思考:假设有1~6物品,看书顺序是214241356。

先看214,对于任意的一个1,2,4的摆放次序,看完2以后必定2在最上面,1和4在下面(顺序不知道),然后看完1,必定1在最上面,接着2,下面是4,再看完4,4在最上面。也就是说,不管1,2,4怎么摆,读完214后必定是从上到下为412。

我们这样考虑:对于1~n的任意不重复看书次序,看i之前,i前面的书都看完了,都在i上面,看完i后,剩下还没有看的都在i下面,后面的每一本书看的时候都必须搬一次i。因此初始摆放序列如果不和看书次序一致,会额外浪费,故要次序一致。

那么,如果有重复的呢?接着上面的例子,考虑214完成后在遇到356之前的重复的2、1和4,因为前3个看完以后一定是上面412,而356还在最下面,故再看214之中的对356不影响。遇到新的书(356)时,分析同上一段。。

故贪心成立。

#include<bits/stdc++.h>
using namespace std;

int n,m,w[1000],b[2000],vis[1000],idx[1000],cnt;
long long ans; 

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=m;i++)cin>>b[i];
	for(int i=1;i<=m;i++)
	{
		if(!vis[b[i]])idx[++cnt]=b[i],vis[b[i]]=1;
	}
	for(int i=1;i<=m;i++)
	{
		int pos=1;
		while(idx[pos]!=b[i])pos++;
		for(int j=1;j<pos;j++)ans+=w[idx[j]];
		int num=idx[pos];
		for(int j=pos;j>1;j--)idx[j]=idx[j-1];
		idx[1]=num;
	}
	cout<<ans<<endl;
	return 0;
}