codeforces703B

Mishka and trip

小米什卡是一个伟大的旅行者，她访问了许多国家。在这次考虑去哪里旅行之后，她选择了XXX--这个美丽，但鲜为人知的北方国家。

以下是关于XXX的一些有趣事实：

XXX由n个城市组成，其中k个（只是想象！）是省会城市。
这个国家的所有城市都很漂亮，但每个城市都很独特。第i个城市的美丽值等于ci。
所有城市通过道路连续连接，包括第1和第n个城市，形成循环路线1 - 2 - … - n - 1
每个省会城市都直接与其他所有城市相连。
任何两个城市之间最多只有一条公路。
通过道路的价格直接取决于它所连接的城市的美丽值。因此，如果城市i和j之间存在道路，则通过它的价格等于ci·cj。

米什卡开始收集她的东西去旅行，但是还没有决定走哪条路线，因此她请求你帮助她确定通过XXX中每条道路的总价格。你会帮她吗？

Input

The first line of the input contains two integers n and k (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n) — the number of cities in XXX and the number of capital cities among them.

The second line of the input contains n integers c₁, c₂, ..., c_n (1 ≤ c_i ≤ 10 000) — beauty values of the cities.

The third line of the input contains k distinct integers id₁, id₂, ..., id_k (1 ≤ id_i ≤ n) — indices of capital cities. Indices are given in ascending order.

Output

Print the only integer — summary price of passing each of the roads in XXX.

Example

Input

4 1
2 3 1 2
3

Output

Input

5 2
3 5 2 2 4
1 4

Output

Note

This image describes first sample case:

$\text{[math]}$

It is easy to see that summary price is equal to 17.

This image describes second sample case:

$\text{[math]}$

It is easy to see that summary price is equal to 71.


sol：比较坑，先O(n)扫一遍求出无省会城市的边权和，然后计算每个省会城市的所有边权和，但这样两个省会城市之间的边权会被统计两次，要把他们去掉
Ps：要小心，把所有相邻的都减掉

/*
一组hack数据
input
3 3
1 1 1
1 2 3
output
3
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=100005;
int n,K,Shengh[N];
ll Cost[N];
int main()
{
    int i;
    ll Sum=0,SS=0,ans=0;
    R(n); R(K);
    for(i=1;i<=n;i++)
    {
        Sum+=(Cost[i]=read());
        if(i>=2) ans+=Cost[i]*Cost[i-1];
    }
    ans+=Cost[1]*Cost[n];
    for(i=1;i<=K;i++)
    {
        SS+=Cost[Shengh[i]=read()];
        ans+=Cost[Shengh[i]]*(Sum-Cost[(Shengh[i]-2+n)%n+1]-Cost[Shengh[i]%n+1]-Cost[Shengh[i]]);
    }
    sort(Shengh+1,Shengh+K+1);
    for(i=1;i<K;i++)
    {
        ll oo=(SS-=Cost[Shengh[i]]);
        if(Shengh[i+1]==Shengh[i]+1) oo-=Cost[Shengh[i+1]];
        if(Shengh[K]==(Shengh[i]-2+n)%n+1) oo-=Cost[Shengh[K]];
        ans-=Cost[Shengh[i]]*oo;
    }
    Wl(ans);
    return 0;
}
/*
input
4 1
2 3 1 2
3
output
17

input
5 2
3 5 2 2 4
1 4
output
71

input
3 3
1 1 1
1 2 3
output
3
*/

View Code