#include using namespace std; using ll = long long; template istream& operator >> (istream& is, vector& vec) { for(T& x : vec) is >> x; return is; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, k, n2; cin >> n >> k; n2 = 2 * n; vector a(n), c(n); vector sa(n2 + 1); cin >> a >> c; a.insert(a.end(), a.begin(), a.end()); c.insert(c.end(), c.begin(), c.end()); for(auto &&v : c) v--; for(int i = 0; i < n2; i++) sa[i + 1] = sa[i] + a[i]; vector> dp(n2 + 1, vector(n2 + 1)); for(int i = 0; i < n2; i++) dp[i][i + 1] = 1ll << c[i]; ll ans = *max_element(a.begin(), a.end()); for(int len = 2; len <= n; len++){ for(int l = 0; l + len < n2; l++){ int r = l + len; for(int m = l + 1; m < r; m++){ dp[l][r] |= dp[l][m] & dp[m][r]; for(int i = 1; i <= k; i++){ dp[l][r] |= dp[l][m] & (dp[m][r] >> k); dp[l][r] |= dp[l][m] & (dp[m][r] << k); dp[l][r] |= (dp[l][m] >> k) & dp[m][r]; dp[l][r] |= (dp[l][m] << k) & dp[m][r]; } } if(dp[l][r]) ans = max(ans, sa[r] - sa[l]); } } cout << ans << '\n'; }