Let's call two adjacent cows "linked" if they are able to pair up with each other. We can split the cows up into chains where each pair of adjacent cows in a chain are linked, and no two cows in different chains are linked.

In each case below, we process each chain independently – let $n$ be the length of the current chain.

Case 1: $T = 1$

For chains with an even number of cows, we can pair up all of them. For chains with an odd number of cows, we want to have exactly 1 unpaired cow. If we leave more than 1 cow unpaired, then we can split the chain into an odd-length suffix with 1 unpaired cow and an even-length prefix with all the other unpaired cows. Since the prefix has an even length, we can pair up all of its cows, which would result in a smaller sum of weights of unpaired cows.

We can thus iterate through each cow in odd-length chains, check whether it can be unpaired (removing it should not result in two odd-length chains), and finally, leave the least valuable cow unpaired.

This case can thus be solved in $\mathcal O(N)$ time.

Case 2: $T = 2$

In this case, we should try to leave unpaired cows in both even- and odd-length chains. We can use dynamic programming to solve this in $\mathcal O(N \log N)$ time.

Let $\texttt{dp}[i][j]$ be the maximum sum of values of unpaired cows if we only consider $i$ to $n$ cows in the current chain and there are $j$ unpaired ones. Let $\texttt{ub}[i]$ be the index of the leftmost cow to the right of cow $i$ that can be unpaired if cow $i$ is unpaired (or $n + 1$ if it doesn't exist). We can compute $\texttt{ub}[i]$ using binary search.

If it's possible to leave cow $i$ unpaired with $j$ unpaired cows, then $\texttt{dp}[i][j] = \max(\texttt{dp}[i + 1][j], \texttt{dp}[\texttt{ub}[i]][j - 1] + y_i)$. Otherwise, $\texttt{dp}[i][j] = \texttt{dp}[i + 1][j]$.

Since we only care about the parity of the number of unpaired cows, we can drop the second dimension of the DP array. This allows us to compute the whole DP array in $\mathcal O(N \log N)$ time (which can easily be reduced to $\mathcal O(N)$).

Andi's code:

#include <algorithm>
#include <array>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

const int INF = 1e9;

int min_span_cost(vector<pair<int, int>>& span, int k) {
    int mn = INF;
    for (int i = 0; i < span.size(); i++) {
        if (!(i & 1) || span[i + 1].first - span[i - 1].first <= k)
            mn = min(mn, span[i].second);
    }
    return mn;
}

int max_span_cost(vector<pair<int, int>>& span, int k) {
    int n = span.size();
    if (!n) return 0;
    vector<pair<int, int>> dp(n + 1);
    dp[n] = {0, -INF};
    for (int i = n - 1; ~i; i--) {
        dp[i] = dp[i + 1];
        int ub = upper_bound(span.begin(), span.end(),
                             make_pair(span[i].first + k, INF)) -
                 span.begin();
        if (i == 0 || i == n - 1 ||
            span[i + 1].first - span[i - 1].first <= k || !(n - i & 1))
            dp[i].first = max(dp[i].first, dp[ub].second + span[i].second);
        if (i == 0 || i == n - 1 ||
            span[i + 1].first - span[i - 1].first <= k || (n - i & 1))
            dp[i].second = max(dp[i].second, dp[ub].first + span[i].second);
    }
    return (n & 1 ? dp[0].second : dp[0].first);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t, n, k;
    cin >> t >> n >> k;
    int prev_x = 0, ans = 0;
    vector<pair<int, int>> curr_span;
    while (n--) {
        int x, y;
        cin >> x >> y;
        if (x - prev_x > k) {
            if (t == 1) {
                if (curr_span.size() & 1) ans += min_span_cost(curr_span, k);
            } else
                ans += max_span_cost(curr_span, k);
            curr_span.clear();
        }
        curr_span.push_back({x, y});
        prev_x = x;
    }
    if (t == 1) {
        if (curr_span.size() & 1) ans += min_span_cost(curr_span, k);
    } else
        ans += max_span_cost(curr_span, k);
    cout << ans;
    return 0;
}