#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ed "\n"
#define int long long
const int N = 2e5 + 5;
int n, k, a[N], h[N], x[N];
namespace sub1 {
bool check() {
return (k == 1);
}
void solve() {
int ans = accumulate(h + 1, h + n + 1, 0LL);
int sum = 0;
for(int i = 1; i <= n; i++) {
sum += min(h[i], abs(x[1] - a[i]));
}
cout << min(ans, sum + 1);
return;
}
}
namespace sub2 {
bool check() {
return (k == 2);
}
void solve() {
// 1: cho tự xử tại chỗ hết
// 2: tự xử tại chỗ và kích nổ tại mìn 1
// 3: tự xử tại chỗ và kích nổ tại mìn 2
// 4: tự xử tại chỗ và kích nổ tại mìn 1 và mìn 2
int ans1 = accumulate(h + 1, h + n + 1, 0LL),
ans2 = 0, ans3 = 0, ans4 = 0;
for(int i = 1; i <= n; i++) {
ans2 += min(h[i], abs(x[1] - a[i]));
ans3 += min(h[i], abs(x[2] - a[i]));
ans4 += min(h[i], min(abs(x[1] - a[i]), abs(x[2] - a[i])));
}
cout << min({ans1, ans2 + 1, ans3 + 1, ans4 + 2});
return;
}
}
namespace sub3 {
bool check() {
return (n <= 18 && k <= 18);
}
void solve() {
int ans = LLONG_MAX;
for(int mask = 0; mask < (1 << k); mask++) {
int res = 0;
for(int i = 0; i < n; i++) {
int cost = h[i + 1];
for(int j = 0; j < k; j++) if(mask >> j & 1) {
cost = min(cost, abs(x[j + 1] - a[i + 1]));
}
res += cost;
}
ans = min(ans, res + __builtin_popcount(mask));
}
cout << ans;
}
}
namespace sub4 {
bool check() {
return (n <= 3000 && k <= 3000);
}
void solve() {
vector<pair<int, int>> s;
for(int i = 1; i <= n; i++) s.push_back({a[i], h[i]});
sort(s.begin(), s.end());
for(int i = 1; i <= n; i++) {
a[i] = s[i - 1].first;
h[i] = s[i - 1].second;
}
sort(x + 1, x + 1 + k);
// dp[i][j][flag] là chi phí tối thiểu để tiêu diệt i quái vật đầu tiên
// bằng cách sử dụng j quả mìn đầu tiên
// flag = 1: quả mìn thứ j đã được kích nổ
// flag = 0: quả mìn thứ j chưa được kích nổ
vector<vector<vector<int>>> dp(n + 2, vector<vector<int>> (k + 2, vector<int> (2, 1e6)));
for(int j = 0; j <= k; j++) dp[0][j][0] = dp[0][j][1] = 0;
for(int i = 1; i <= n; i++) {
dp[i][0][0] = dp[i - 1][0][0] + h[i];
for(int j = 1; j <= k; j++) {
for(int flag = 0; flag < 2; flag++) {
dp[i][j][flag] = dp[i - 1][j][flag] + h[i];
dp[i][j][flag] = min(dp[i][j][flag], dp[i - 1][j][1] + abs(x[j] - a[i]) + 1 - flag);
dp[i][j][flag] = min(dp[i][j][flag], dp[i][j - 1][0]);
}
}
}
cout << dp[n][k][0];
}
}
void solve(int iTest) {
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i] >> h[i];
for(int i = 1; i <= n; i++) cin >> x[i];
if(sub1::check()) sub1::solve();
else if(sub2::check()) sub2::solve();
// else if(sub3::check()) sub3::solve();
else if(sub4::check()) sub4::solve();
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#define TASK "main"
if(fopen(TASK ".inp", "r")) {
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
else if(fopen("main.inp", "r")) {
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
}
int T = 1;
// cin >> T;
for(int iTest = 1; iTest <= T; iTest++) {
solve(iTest);
}
}
