题意

数轴上有 $k$ 个点是草地，每个草地有不同收益， $m$ 个点是地方的点，现在你要放置 $n$ 个我方的点，不能和敌方的点重合。

如果一个草地离最近的我方的点距离严格小于最近的敌方点距离，那么这个草地被占领。

给出敌方点和草地坐标（保证两两不同），求占领草地的最大收益和 。

$1\leq n,m,k\leq 2\times10^5,1\leq x\leq 10^9$ 。

题解

考虑两两敌方点间的草地。之间最多放两个点就可以把草地全部收入囊中，1 个点就要考虑双指针扫最大价值。因为两点的价值一定小于等于一点的两倍，于是可以贪心，堆维护，每次取出的如果是一点的，就把两点塞进去，做 $n$ 次。

代码

const int N = 2e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	#define mp make_pair
	struct node {
		ll p, t;
	} a[N];
	ll n, m, k, ans, s[N], f[N], w[N], v[N];
	priority_queue<pair<ll, ll> > q;
	
	int main() {
		k = Read(), m = Read(), n = Read();
		for (int i = 1; i <= k; i++) a[i].p = Read(), a[i].t = Read();
		for (int i = 1; i <= m; i++) f[i] = Read();
		sort(a + 1, a + 1 + k, [](node x, node y) { return x.p < y.p; });
		sort(f + 1, f + 1 + m);
		f[0] = -1e9, f[m + 1] = 2e9;
		ll now = 1, l = 1, lst = 0, maxs = 0;
		for(int i = 1; i <= k; i++) {
			s[i] = s[i - 1] + a[i].t;
			while(l <= m && f[l] < a[i].p) {
				w[l] = maxs;
				v[l] = s[i - 1] - s[lst];
				lst = i - 1;
				now = i;
				maxs = 0;
				l++;
			}
			ll L = f[l - 1], R = f[l];
			while((a[i].p - a[now].p) * 2 >= R - L) now++;
			maxs = max(maxs, s[i] - s[now - 1]);
		}
		w[l] = maxs;
		v[l] = s[n] - s[lst];
		for (int i = 0; i <= k + 1; i++)
			q.push(mp(w[i], i));
		for (int i = 1; i <= n; i++) {
			pair<ll, ll> w = q.top();
			ans += w.first;
			q.pop();
			if(w.second) q.push(mp(v[w.second] - w.first, 0));
		}
		printf("%lld\n", ans);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}