#include <bits/stdc++.h> #define int long long #define debug cout << "ok\n"; #define SQR(x) (1LL * ((x) * (x))) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define fi first #define se second #define pb push_back #define mp make_pair #define pii pair<int,int> #define pli pair<ll,int> #define vi vector<int> #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef unsigned int ui; using namespace std; const int M = 1e9 + 7; const int INF = 1e9 + 7; const ll INFLL = (ll)2e18 + 7LL; const ld PI = acos(-1); const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1}; const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1}; template<class _, class __> bool minimize(_ &x, const __ y){ if(x > y){ x = y; return true; } else return false; } template<class _, class __> bool maximize(_ &x, const __ y){ if(x < y){ x = y; return true; } else return false; } template<class _,class __> void Add(_ &x, const __ y) { x += y; if (x >= M) { x -= M; } return; } template<class _,class __> void Diff(_ &x, const __ y) { x -= y; if (x < 0) { x += M; } return; } //-------------------------------------------------------------- const int MaxN = 1e6+7; int n,K,a[MaxN],b[MaxN],f[MaxN],t[MaxN],lst[MaxN]; vi lis[MaxN]; vi nen; struct FenwickTree { vi FW; int n; void Set(int _n) { n = _n; FW.assign(n+1,0); } int Get(int u) { int res = 0; for (;u;u-=u&-u) { res += FW[u]; } return res; } int Get(int l,int r) { return Get(r) - Get(l-1); } void Upd(int u,int v) { for (;u<=n;u+=u&-u) { FW[u] += v; } } } Fw; struct SegmentTree { vi Tr; int n; void Set(int _n) { n = _n; Tr.assign(n*4+7,0); } void UT(int id,int l,int r,int u,int v) { if (l > u || r < u) return; if (l == r) { maximize(Tr[id],v); return; } int m = (l+r) >> 1; UT(id<<1,l,m,u,v); UT(id<<1|1,m+1,r,u,v); Tr[id] = max(Tr[id<<1],Tr[id<<1|1]); } int GV(int id,int l,int r,int ls,int rs) { if (l > rs || r < ls) return 0; if (ls <= l && r <= rs) return Tr[id]; int m = (l+r) >> 1; return max(GV(id<<1,l,m,ls,rs),GV(id<<1|1,m+1,r,ls,rs)); } int Get(int l,int r) { return GV(1,1,n,l,r); } void Upd(int u,int v) { UT(1,1,n,u,v); } } Seg; void sol() { cin >> n >> K; for (int i=1;i<=n;i++) { cin >> a[i] >> b[i]; if (a[i] > b[i]) { swap(a[i],b[i]); f[i] = 1; } nen.pb(a[i]); nen.pb(b[i]); } for (int i=1;i<=K;i++) { cin >> t[i]; nen.pb(t[i]); } sort(nen.begin(),nen.end()); nen.erase(unique(nen.begin(),nen.end()),nen.end()); for (int i=1;i<=n;i++) { a[i] = lower_bound(nen.begin(),nen.end(),a[i]) - nen.begin() + 1; b[i] = lower_bound(nen.begin(),nen.end(),b[i]) - nen.begin() + 1; } for (int i=1;i<=K;i++) { t[i] = lower_bound(nen.begin(),nen.end(),t[i]) - nen.begin() + 1; } Seg.Set(nen.size()); for (int i=1;i<=K;i++) { Seg.Upd(t[i],i); } for (int i=1;i<=n;i++) { lst[i] = Seg.Get(a[i],b[i]-1); lis[lst[i]].pb(i); if (lst[i]) f[i] = 1; } Fw.Set(nen.size()); t[0] = 1; for (int i=K;i>=0;i--) { for (int u : lis[i]) { f[u] += Fw.Get(b[u],nen.size()); } Fw.Upd(t[i],1); } int res = 0; for (int i=1;i<=n;i++) { if (f[i] & 1) res += nen[b[i]-1]; else res += nen[a[i]-1]; } cout << res; } signed main() { // freopen("test.inp","r",stdin); // freopen("test.out","w",stdout); FAST int t=1; // cin >> t; while (t--) sol(); }