analysis
我们首先通过读题就可以得出，我们要想走到下一层，必须先将这一层里面的所有宝藏都拿完。我们又可以想到，我们一定是直接从一端走到另外一端这样子才能保证在这一层中的花费时间最小。
所以对于每一层来说，我们只需要记录左右两个端点就好了。
对于每一个安全列来说，我们在通往下一层的时候都得要先走到这一列上，然后再转移到下一层之后，再转移到下一层得端点位置。
我们现在的问题就已经简化成了：
如何让我从一层转移到另外一层的花费最小。
我们就可以考虑存储一个前缀，表示这个列前面得第一个安全列得位置在哪里；同时存储一个后缀，表示这个列后面得第一个安全列在哪里。
我们得转移方程就呼之欲出（calc 函数用来求从这个端点到下一层端点得最近距离。）：
\[f_{i, 0} \gets min(f_{i - 1, 1} + calc(l_i, r_{i - 1}), f_{i - 1, 0} + calc(l_i, l_{i - 1}))
\]
\[f_{i, 1} \gets min(f_{i - 1, 1} + calc(r_i, r_{i - 1}, f_{i - 1, 0} + calc(r_i, l_{i - 1}))
\]
code time
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll
#define foa(i, a, b) for(rl i=a; i < b; ++ i)
#define fos(i, a, b) for(rl i=a; i <= b; ++ i)
#define fop(i, a, b) for(rl i=a; i >= b; -- i)
#define ws putchar(' ')
#define wl putchar('\n')
template <class T> inline void waw(T x)
{
if(x > 9) waw(x / 10);
putchar(x % 10 ^ 48);
}
template <class T> inline void ww(T x)
{
if(x < 0) x = ~x + 1, putchar('-');
waw(x);
}
template <class T> inline void read(T &res)
{
char ch = getchar(); bool f = 0; res = 0;
for(; !isdigit(ch); ch = getchar()) f |= ch == '-';
for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);
res = f ? ~res + 1 : res;
}
const ll N = 2e5 +10;
ll f[N][2], l[N], r[N], pre[N], nxt[N], n, m;
bool sf[N];
inline ll calc(ll x, ll y)
{
if(x > y) swap(x, y);
if(pre[y] >= x) return y - x;
ll res = 1e18;
if(pre[x]) res = min(res, y + x - (pre[x] << 1));
if(nxt[y]) res = min(res, (nxt[y] << 1) - x - y);
return res;
}
int main()
{
ll c, d; read(n), read(m), read(c), read(d);
n = m = 0;
fos(i, 1, c)
{
ll x, y; read(x), read(y);
n = max(n, x), m = max(m, y);
l[x] = l[x] ? min(l[x], y) : y;
r[x] = r[x] ? max(r[x], y) : y;
}
if(!l[1]) l[1] = r[1] = 1;
memset(f, 0x3f, sizeof f);
fos(i, 1, d) { ll x; read(x); m = max(m, x), sf[x] = 1; }
fos(i, 1, m) pre[i] = sf[i] ? i : pre[i - 1];
fop(i, m, 1) nxt[i] = sf[i] ? i : nxt[i + 1];
f[1][0] = (r[1] << 1) - 1 - l[1], f[1][1] = r[1] - 1;
fos(i, 2, n)
{
if(!l[i])
{
l[i] = l[i - 1], r[i] = r[i-1], f[i][0] = f[i-1][0], f[i][1] = f[i-1][1];
continue;
}
f[i][0] = min(f[i-1][0] + calc(l[i], l[i-1]), f[i-1][1] + calc(r[i-1], l[i]));
f[i][1] = min(f[i-1][0] + calc(r[i], l[i-1]), f[i-1][1] + calc(r[i-1], r[i]));
swap(f[i][0], f[i][1]); f[i][0] += r[i] - l[i], f[i][1] += r[i] - l[i];
}
ww(min(f[n][0], f[n][1]) + n - 1), wl;
return 0;
}