#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/**
* JOI Open Contest 2014 - Fortune Telling 2
* Karmaşıklık: O((N + K) log K + (N + K) log (N + K))
*/
const int MAX = 600005;
int tree[4 * MAX];
// Segment Tree: Belirli bir aralıktaki maksimum T_j indeksini bulmak için
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid) update(2 * node, start, mid, idx, val);
else update(2 * node + 1, mid + 1, end, idx, val);
tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return -1;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return max(query(2 * node, start, mid, l, r), query(2 * node + 1, mid + 1, end, l, r));
}
// Fenwick Tree: Kritik operasyondan sonraki ters çevirme sayılarını toplamak için
int bit[MAX];
void bit_update(int idx, int val, int n) {
for (; idx <= n; idx += idx & -idx) bit[idx] += val;
}
int bit_query(int idx) {
int res = 0;
for (; idx > 0; idx -= idx & -idx) res += bit[idx];
return res;
}
struct Card {
int a, b, id;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K; [cite: 24]
vector<Card> cards(N);
for (int i = 0; i < N; i++) {
cin >> cards[i].a >> cards[i].b; [cite: 25]
cards[i].id = i;
}
vector<int> T(K);
vector<int> coords;
for (int i = 0; i < K; i++) {
cin >> T[i]; [cite: 27]
coords.push_back(T[i]);
}
// Koordinat sıkıştırma için tüm değerleri topla
for (int i = 0; i < N; i++) {
coords.push_back(cards[i].a);
coords.push_back(cards[i].b);
}
sort(coords.begin(), coords.end());
coords.erase(unique(coords.begin(), coords.end()), coords.end());
auto get_id = [&](int x) {
return lower_bound(coords.begin(), coords.end(), x) - coords.begin() + 1;
};
int M = coords.size();
for (int i = 0; i < K; i++) {
update(1, 1, M, get_id(T[i]), i + 1);
}
vector<vector<int>> queries_at(K + 1);
vector<int> last_op(N);
for (int i = 0; i < N; i++) {
int l = min(cards[i].a, cards[i].b);
int r = max(cards[i].a, cards[i].b);
// A_i ve B_i arasındaki son T_j'yi bul
int op = query(1, 1, M, get_id(l), get_id(r) - 1);
if (op == -1) last_op[i] = 0;
else last_op[i] = op;
queries_at[last_op[i]].push_back(i);
}
long long total_sum = 0;
// Operasyonları sondan başa doğru tarayarak Fenwick Tree ile kalanları hesapla
for (int j = K; j >= 0; j--) {
if (j > 0) {
bit_update(get_id(T[j - 1]), 1, M);
}
for (int card_idx : queries_at[j]) {
int current_a = cards[card_idx].a;
int current_b = cards[card_idx].b;
// Eğer bir kritik operasyon varsa, o andaki durumu belirle
if (j > 0) {
// T_j >= min(a,b) olduğu için büyük olan değer üste gelir
current_a = max(cards[card_idx].a, cards[card_idx].b);
current_b = min(cards[card_idx].a, cards[card_idx].b);
}
// Kritik operasyondan sonra kaç tane T_k >= current_a var?
int flips = bit_query(M) - bit_query(get_id(max(current_a, current_b)) - 1);
if (flips % 2 == 1) total_sum += current_b;
else total_sum += current_a;
}
}
cout << total_sum << endl; [cite: 36]
return 0;
}
