#include <iostream> #include <vector> using namespace std; using ll = long long; using ull = unsigned long long; int main () { // 色と場所を持って区間dpできそう -> 間に合わないが、真偽値によるdpであることを考えるとワードサイズ分の高速化が効く int N, K; cin >> N >> K; vector<int> 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<vector<ull>> dp(N, vector<ull>(N+1, 0)); // dp[i][j] := iから右回りにj個の区間を全統合したとき、作成可能な色のセット for (int i = 0; i < N; i++) dp[i][1] = 1ull<<C[i]; ull mask = (1ull<<50) - 1; for (int j = 2; j <= N; j++) { for (int i = 0; i < N; i++) { for (int mid = 1; mid < j; mid++) { // 右シフト or 左シフト for (int k = 0; k <= K; k++) { dp[i][j] |= dp[i][mid] & (dp[(i+mid) % N][j-mid] >> k); dp[i][j] |= (dp[i][mid] >> k) & dp[(i+mid) % N][j-mid]; dp[i][j] |= dp[i][mid] & (dp[(i+mid) % N][j-mid] << k); dp[i][j] |= (dp[i][mid] << k) & dp[(i+mid) % N][j-mid]; } } dp[i][j] &= mask; } } ll ans = 0; for (int i = 0; i < N; i++) for (int j = 1; j <= N; j++) for (int c = 0; c < 50; c++) if (0 < dp[i][j]) { ll sum = 0; for (int k = 0; k < j; k++) sum += A[(i + k) % N]; ans = max(ans, sum); } cout << ans << "\n"; }