https://csacademy.com/contest/round-19/#task/cities-robbery

$1$次元上に$N$個の都市があり，それぞれ座標が$x_i$で価値が$w_i$である．$X$にいて，$K$動くことが出来るときに，得られる価値の和を最大化する．

現在の位置よりも右側にいるのか，左側にいるのかで分けて持つ．右側を折り返して左側に行くパターンと，左側を折り返して右側に行くパターンの$2$つに分かれる．何個まで持つかを配列にして持っておけば，価値にマイナスはないので単調増加列になるため，片方を決め打ちすると，残りの距離からその場合の最大の価値を二分探索で求めることができる．$(0, 0)$を追加して片方を何も取らない場合も一緒にした．

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int,ll> P;

int main() {
	int n, x, k;
	cin >> n >> x >> k;

	ll start = 0;
	vector<P> v(n);
	rep(i, n) {
		cin >> v[i].fi >> v[i].se;
		v[i].fi -= x;
	}

	vector<P> a, b;
	rep(i, n) {
		if(v[i].fi == 0) start += v[i].se;

		if(v[i].fi < 0) a.push_back(mp(-v[i].fi, v[i].se));
		else b.push_back(v[i]);
	}

	a.push_back(mp(0, 0));
	sort(a.begin(), a.end());

	b.push_back(mp(0, 0));
	sort(b.begin(), b.end());

	vector<ll> aid(a.size());
	vector<ll> aval(a.size());
	rep(i, a.size()) {
		aid[i] = a[i].fi;
		aval[i] = a[i].se;
	}

	REP(i, 1, a.size()) aval[i] += aval[i-1];

	vector<ll> bid(b.size());
	vector<ll> bval(b.size());
	rep(i, b.size()) {
		bid[i] = b[i].fi;
		bval[i] = b[i].se;
	}

	REP(i, 1, b.size()) bval[i] += bval[i-1];

	ll ans = 0;
	rep(i, a.size()) {
		if(aid[i] > k) break;
		ans = max(ans, aval[i] + start);

		// aからi個とる
		ll diff = k - 2 * aid[i];
		
		if(diff < 0) continue;

		vector<ll>::iterator it = upper_bound(bid.begin(), bid.end(), diff);
		if(it == bid.end()) {
			ans = max(ans, aval[i] + start + bval[bval.size()-1]);
		} else {
			int id = (it - bid.begin());
			if(id == 0) continue;
			id--;

			ans = max(ans, aval[i] + start + bval[id]);
		}
	}

	rep(i, b.size()) {
		if(bid[i] > k) break;
		ans = max(ans, bval[i] + start);

		// aからi個とる
		ll diff = k - 2 * bid[i];

		if(diff < 0) continue;

		vector<ll>::iterator it = upper_bound(aid.begin(), aid.end(), diff);
		if(it == aid.end()) {
			ans = max(ans, bval[i] + start + aval[aval.size()-1]);
		} else {
			int id = (it - aid.begin());
			if(id == 0) continue;
			id--;

			ans = max(ans, bval[i] + start + aval[id]);
		}
	}

	cout << ans << endl;

	return 0;
}