\(Solution\)

考慮 dp。

觀察數據范圍，\(n,k\leq 500\) 的數據幾乎明示了同階下 \(\Theta(n^3)\) 的算法了。那么直接往這里考慮。

設 \(f_{i,j}\) 為當前是第 \(i\) 中顏色，且已經選了 \(j\) 種顏色的最大值。

那么有以下轉移方程：

其中 \(cmp\) 函數為判斷兩個顏色是否有交叉段，即是否呈單調不下降序列。當然這兩個顏色必須存在。

那么我們記兩個數組 \(front,back\) 為當前顏色最早和最后出現的位置即可。

\(\mathcal{Code}\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 500 + 5;
int a[N], b[N], up[N], down[N], ans, f[N][N];
signed main() {
	auto read = [&]() -> auto {
		int x = 0, m = 1;
		char ch = getchar();
		while (!isdigit(ch)) {
			if (ch == '-') m = -1;
			ch = getchar();
		}
		while (isdigit(ch)) {
			x = x * 10 + ch - 48;
			ch = getchar();
		}
		return x * m;
	};

	function<void(int)> write = [&](int x) {
		if (x < 0) {
			putchar('-');
			write(-x);
			return ;
		}
		if (x >= 10) write(x / 10);
		putchar(x % 10 + '0');
	};

	auto writeln = [&](int x) -> auto {
		write(x), putchar('\n');
	};

	auto writesp = [&](int x) -> auto {
		write(x), putchar(' ');
	};

	int n = read(), m = read();
	for(int i = 1; i <= n; i ++) {
		a[i] = read();
		if(!up[a[i]]) up[a[i]] = i;
	}
	for(int i = n; i; i --) if(!down[a[i]]) down[a[i]] = i;
	for(int i = 1; i <= n; i ++) b[i] = read();
	for(int i = 1; i <= n; i ++) {
		f[i][1] = b[i];
		for(int j = 1; j < i; j ++) {
			if(down[j] > up[i] || !down[j] || !up[i]) continue;
			for(int k = 2; k <= m; k ++) {
				if(!f[j][k - 1]) continue;
				f[i][k] = max(f[i][k], f[j][k - 1] + b[i]);
			}
		}
		ans = max(ans, f[i][m]);
	}
	if(!ans) cout << -1 << '\n';
	else cout << ans << '\n';
	return 0;
}