读其他题解读了好久才懂……
首先，因为匹配的顺序不重要，所以我们规定匹配不允许交叉，必须相邻两个没有删掉的匹配。
开始考虑动态规划。$f_{i,j}$ 表示前 $i$ 头奶牛，有 $j$ 头未匹配的最小重量和。
转移分以下四种情况：

• $i-j$ 是偶数，且 $i$ 不匹配。这种情况下，所有在 $i$ 前面的奶牛，如果和第 $i$ 头奶牛距离不超过 $K$，都应该匹配了，因为题目中说匹配是极大的。设 $lst$ 是满足 $x_i - x_{lst} > K$ 中最大的，那么上一头不参加匹配的奶牛肯定在 $lst$ 或 $lst$ 的左边，则这种情况的转移为 $f_{i,j} \xleftarrow[x_i-x_{lst}>K]{+y_i} f_{lst,j-1}$。
• $i-j$ 是偶数，且 $i$ 匹配。这种情况下，因为匹配不允许交叉，所以 $i$ 前面等待和 $i$ 匹配的肯定是 $i-1$ 或 $i-2$ 头奶牛。原因：如果是 $i-3$ 等待匹配，那么 $i-1$ 和 $i-2$ 肯定都不参与匹配。$i$ 和 $i-3$ 距离不超过 $K$，那么 $i-1$ 和 $i-2$ 的距离也不超过 $K$，即 $i-1$ 和 $i-2$ 可以组成一组匹配，与题目要求不符，命题得证。但转移的时候我们只需要从 $f_{i-1,j}$ 转移过来，因为 $i-2$ 与 $i$ 匹配的情况会在下面第 $3$ 种转移中考虑进 $f_{i-1,j}$。则这种情况的转移为 $f_{i,j} \xleftarrow[x_i-x_{i-1}\le K]{} f_{i-1,j}$。
• $i-j$ 是奇数，且 $i$ 不匹配。这种情况下，基本和第 $1$ 种情况同理，不过这次最右边的匹配是 $i-1$ 和 $i+1$ 匹配。因为如果 $i-1$ 也不参与匹配，前面肯定有一组匹配跨越了 $i-1$ 和 $i$，和第 $2$ 种转移中的证明类似，这种情况与题目要求不符。则转移为 $f_{i,j} \xleftarrow [x_{i+1}-x_{i-1}\le K \land x_i-x_{lst}>K]{+y_i} f_{lst,1-j}$。
• $i-j$ 是奇数，且 $i$ 匹配。这种情况下，$i$ 只能和 $i+1$ 或 $i+2$ 匹配。和 $i+2$ 匹配的情况会在第三种转移时考虑进 $f_{i+1}$，所以这里只考虑和 $i+1$ 匹配即可。转移为 $f_{i,j} \xleftarrow [x_{i+1}-x_i \le K]{} f_{i-1,j}$。

状态、转移搞出来，其他就简单了。观察到转移只和 $j$ 的奇偶性有关，可以把状态简化。
取答案、赋初值、最大最小自己处理。
时间复杂度 $\mathcal{O}(N)$。
代码：

	for (int i = 1; i <= n; i++) {
		while (lst + 1 < i && a[i][0] - a[lst + 1][0] > k) {
			lst++;
		}
		for (int j = 0; j < 2; j++) {
			if (!((i - j) & 1)) {
				f[i][j] = min(f[i][j], f[lst][1 - j] + a[i][1]);
				if (a[i][0] - a[i - 1][0] <= k) {
					f[i][j] = min(f[i][j], f[i - 1][j]);
				}
			} else {
				if (i < n && a[i + 1][0] - a[i - 1][0] <= k) {
					f[i][j] = min(f[i][j], f[lst][1 - j] + a[i][1]);
				}
				if (i < n && a[i + 1][0] - a[i][0] <= k) {
					f[i][j] = min(f[i][j], f[i - 1][j]);
				}
			}
		}
	}