Let’s denote the following function $f$. This function takes an array $a$ of length $n$ and returns an array. Initially the result is an empty array. For each integer $i$ from $1$ to $n$ we add element $a_i$ to the end of the resulting array if it is greater than all previous elements (more formally, if $a_i > \max\limits_{1 \le j < i}a_j$). Some examples of the function $f$:
- if $a = [3, 1, 2, 7, 7, 3, 6, 7, 8]$ then $f(a) = [3, 7, 8]$;
- if $a = [1]$ then $f(a) = [1]$;
- if $a = [4, 1, 1, 2, 3]$ then $f(a) = [4]$;
- if $a = [1, 3, 1, 2, 6, 8, 7, 7, 4, 11, 10]$ then $f(a) = [1, 3, 6, 8, 11]$.
You are given two arrays: array $a_1, a_2, \dots , a_n$ and array $b_1, b_2, \dots , b_m$. You can delete some elements of array $a$ (possibly zero). To delete the element $a_i$, you have to pay $p_i$ coins (the value of $p_i$ can be negative, then you get $|p_i|$ coins, if you delete this element). Calculate the minimum number of coins (possibly negative) you have to spend for fulfilling equality $f(a) = b$.
Input
The first line contains one integer $n$ $(1 \le n \le 5 \cdot 10^5)$ — the length of array $a$.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le n)$ — the array $a$.
The third line contains $n$ integers $p_1, p_2, \dots, p_n$ $(|p_i| \le 10^9)$ — the array $p$.
The fourth line contains one integer $m$ $(1 \le m \le n)$ — the length of array $b$.
The fifth line contains $m$ integers $b_1, b_2, \dots, b_m$ $(1 \le b_i \le n, b_{i-1} < b_i)$ — the array $b$.
Output
If the answer exists, in the first line print YES. In the second line, print the minimum number of coins you have to spend for fulfilling equality $f(a) = b$.
Otherwise in only line print NO.
Examples
input
11 4 1 3 3 7 8 7 9 10 7 11 3 5 0 -2 5 3 6 7 8 2 4 3 3 7 10
output
YES 20
input
6 2 1 5 3 6 5 3 -9 0 16 22 -14 4 2 3 5 6
output
NO
Solution:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=501000;
struct node {
ll fg;
ll val;
}nd[4*N];
void upd(int p) {
}
void setf(int p,ll v) {
nd[p].fg+=v;
nd[p].val+=v;
}
void build(int p,int l,int r) {
nd[p].fg=0;
nd[p].val=1ll<<60;
if (l==r) {
if (l==0) nd[p].val=0;
} else {
int md=(l+r)>>1;
build(p+p,l,md);
build(p+p+1,md+1,r);
upd(p);
}
}
void push(int p) {
if (nd[p].fg) {
setf(p+p,nd[p].fg);
setf(p+p+1,nd[p].fg);
nd[p].fg=0;
}
}
ll query(int p,int l,int r,int x) {
if (l==r) return nd[p].val;
else {
push(p);
int md=(l+r)>>1;
if (x<=md) return query(p+p,l,md,x);
else return query(p+p+1,md+1,r,x);
}
}
void modify(int p,int l,int r,int tl,int tr,ll v) {
if (tl>tr) return;
if (tl==l&&tr==r) return setf(p,v);
else {
push(p);
int md=(l+r)>>1;
if (tr<=md) modify(p+p,l,md,tl,tr,v);
else if (tl>md) modify(p+p+1,md+1,r,tl,tr,v);
else modify(p+p,l,md,tl,md,v),modify(p+p+1,md+1,r,md+1,tr,v);
upd(p);
}
}
int n,a[N],p[N],b[N],m;
int main() {
scanf("%d",&n);
rep(i,1,n+1) scanf("%d",a+i);
rep(i,1,n+1) scanf("%d",p+i);
scanf("%d",&m);
rep(i,1,m+1) scanf("%d",b+i);
b[m+1]=1<<30;
build(1,0,m);
rep(i,1,n+1) {
int j=lower_bound(b+1,b+m+1,a[i])-b;
if (b[j]==a[i]) {
modify(1,0,m,j+1,m,min(p[i],0));
ll a=query(1,0,m,j);
ll x=a+min(p[i],0),y=query(1,0,m,j-1);
modify(1,0,m,j,j,min(x,y)-a);
modify(1,0,m,0,j-1,p[i]);
} else {
modify(1,0,m,j,m,min(p[i],0));
modify(1,0,m,0,j-1,p[i]);
}
//rep(j,0,m+1) printf("%lld ",query(1,0,m,j));
//puts("");
}
ll a=query(1,0,m,m);
if (a>=1ll<<55) puts("NO"); else printf("YES\n%lld\n",a);
}
