#include #include using namespace std; using ll = long long; int main () { // 色と場所を持って区間dpできそう int N, K; cin >> N >> K; vector A(N), C(N); for (int i = 0; i < N; i++) cin >> A[i]; for (int i = 0; i < N; i++) cin >> C[i]; for (int i = 0; i < N; i++) C[i]--; vector>> dp(N, vector>(N+1, vector(50, 0))); // dp[i][j][c] := iから右回りにj個の区間を全統合し、結果色cの石を作ったとき、価値の最大 for (int i = 0; i < N; i++) dp[i][1][C[i]] = A[i]; for (int j = 2; j <= N; j++) { for (int i = 0; i < N; i++) { for (int mid = 1; mid < j; mid++) { for (int c = 0; c < 50; c++) { for (int k = 0; k <= K; k++) { if (0 < dp[i][mid][c] && 0 < dp[(i+mid)%N][j-mid][min(49, c+k)]) { dp[i][j][c] = max(dp[i][j][c], dp[i][mid][c] + dp[(i+mid)%N][j-mid][min(49, c+k)]); } if (0 < dp[i][mid][c] && 0 < dp[(i+mid)%N][j-mid][max(0, c-k)]) { dp[i][j][c] = max(dp[i][j][c], dp[i][mid][c] + dp[(i+mid)%N][j-mid][max(0, c-k)]); } if (0 < dp[i][mid][min(49, c+k)] && 0 < dp[(i+mid)%N][j-mid][c]) { dp[i][j][c] = max(dp[i][j][c], dp[i][mid][min(49, c+k)] + dp[(i+mid)%N][j-mid][c]); } if (0 < dp[i][mid][c] && 0 < dp[(i+mid)%N][j-mid][max(0, c-k)]) { dp[i][j][c] = max(dp[i][j][c], dp[i][mid][max(0, c-k)] + dp[(i+mid)%N][j-mid][c]); } } } } } } ll ans = 0; for (int i = 0; i < N; i++) for (int j = 1; j <= N; j++) for (int c = 0; c < 50; c++) ans = max(ans, dp[i][j][c]); cout << ans << "\n"; }