#include using namespace std; using pint = pair; using pll = pair; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } #define REP(i, n) for (long long i = 0; i < (long long)(n); ++i) #define REP2(i, a, b) for (long long i = a; i < (long long)(b); ++i) #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl template ostream& operator << (ostream &s, pair P) { return s << '<' << P.first << ", " << P.second << '>'; } template ostream& operator << (ostream &s, set P) { for(auto it : P) { s << "" << it << " "; } return s; } template ostream& operator << (ostream &s, vector P) { for (int i = 0; i < P.size(); ++i) { s << "{"; if (i > 0) { s << " "; } s << P[i] << "}, "; } return s; } template ostream& operator << (ostream &s, deque P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template ostream& operator << (ostream &s, vector > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template ostream& operator << (ostream &s, multiset P) { for(auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, map P) { for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } /*///////////////////////////////////////////////////////*/ // Union-Find, modint, segtree, lazy segtree /*///////////////////////////////////////////////////////*/ // 4-neighbor (or 8-neighbor) const vector dx = {1, 0, -1, 0, 1, -1, 1, -1}; const vector dy = {0, 1, 0, -1, 1, 1, -1, -1}; // Union-Find struct UnionFind { // core member vector par; // constructor UnionFind() { } UnionFind(int n) : par(n, -1) { } void init(int n) { par.assign(n, -1); } // core methods int root(int x) { if (par[x] < 0) return x; else return par[x] = root(par[x]); } bool same(int x, int y) { return root(x) == root(y); } bool merge(int x, int y) { x = root(x), y = root(y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); // merge technique par[x] += par[y]; par[y] = x; return true; } int size(int x) { return -par[root(x)]; } // debug friend ostream& operator << (ostream &s, UnionFind uf) { map> groups; for (int i = 0; i < uf.par.size(); ++i) { int r = uf.root(i); groups[r].push_back(i); } for (const auto &it : groups) { s << "group: "; for (auto v : it.second) s << v << " "; s << endl; } return s; } }; // modint template struct Fp { // inner value long long val; // constructor constexpr Fp() noexcept : val(0) { } constexpr Fp(long long v) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr long long get() const noexcept { return val; } constexpr int get_mod() const noexcept { return MOD; } // arithmetic operators constexpr Fp operator - () const noexcept { return val ? MOD - val : 0; } constexpr Fp operator + (const Fp &r) const noexcept { return Fp(*this) += r; } constexpr Fp operator - (const Fp &r) const noexcept { return Fp(*this) -= r; } constexpr Fp operator * (const Fp &r) const noexcept { return Fp(*this) *= r; } constexpr Fp operator / (const Fp &r) const noexcept { return Fp(*this) /= r; } constexpr Fp& operator += (const Fp &r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator -= (const Fp &r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp& operator *= (const Fp &r) noexcept { val = val * r.val % MOD; return *this; } constexpr Fp& operator /= (const Fp &r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr Fp pow(long long n) const noexcept { Fp res(1), mul(*this); while (n > 0) { if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } constexpr Fp inv() const noexcept { Fp res(1), div(*this); return res / div; } // other operators constexpr bool operator == (const Fp &r) const noexcept { return this->val == r.val; } constexpr bool operator != (const Fp &r) const noexcept { return this->val != r.val; } friend constexpr istream& operator >> (istream &is, Fp &x) noexcept { is >> x.val; x.val %= MOD; if (x.val < 0) x.val += MOD; return is; } friend constexpr ostream& operator << (ostream &os, const Fp &x) noexcept { return os << x.val; } friend constexpr Fp modpow(const Fp &r, long long n) noexcept { return r.pow(n); } friend constexpr Fp modinv(const Fp &r) noexcept { return r.inv(); } }; // Binomial coefficient template struct BiCoef { vector fact_, inv_, finv_; constexpr BiCoef() {} constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) { init(n); } constexpr void init(int n) noexcept { fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); int MOD = fact_[0].get_mod(); for(int i = 2; i < n; i++){ fact_[i] = fact_[i-1] * i; inv_[i] = -inv_[MOD%i] * (MOD/i); finv_[i] = finv_[i-1] * inv_[i]; } } constexpr T com(int n, int k) const noexcept { if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n-k]; } constexpr T fact(int n) const noexcept { if (n < 0) return 0; return fact_[n]; } constexpr T inv(int n) const noexcept { if (n < 0) return 0; return inv_[n]; } constexpr T finv(int n) const noexcept { if (n < 0) return 0; return finv_[n]; } }; // Segment Tree template struct SegTree { using Func = function; // core member int SIZE; Func F; Monoid IDENTITY; // data int offset; vector dat; // constructor SegTree() {} SegTree(int n, const Func &f, const Monoid &identity) : SIZE(n), F(f), IDENTITY(identity) { offset = 1; while (offset < n) offset *= 2; dat.assign(offset * 2, IDENTITY); } void init(int n, const Func &f, const Monoid &identity) { SIZE = n; F = f; IDENTITY = identity; offset = 1; while (offset < n) offset *= 2; dat.assign(offset * 2, IDENTITY); } int size() const { return SIZE; } // set, a is 0-indexed // // build(): O(N) void set(int a, const Monoid &v) { dat[a + offset] = v; } void build() { for (int k = offset - 1; k > 0; --k) dat[k] = F(dat[k*2], dat[k*2+1]); } void build(const vector &vec) { for (int a = 0; a < vec.size() && a + offset < dat.size(); ++a) set(a, vec[a]); build(); } // update a, a is 0-indexed, O(log N) void update(int a, const Monoid &v) { int k = a + offset; dat[k] = v; while (k >>= 1) dat[k] = F(dat[k*2], dat[k*2+1]); } // get [a, b), a and b are 0-indexed, O(log N) Monoid get(int a, int b) { Monoid vleft = IDENTITY, vright = IDENTITY; for (int left = a + offset, right = b + offset; left < right; left >>= 1, right >>= 1) { if (left & 1) vleft = F(vleft, dat[left++]); if (right & 1) vright = F(dat[--right], vright); } return F(vleft, vright); } Monoid get_all() { return dat[1]; } Monoid operator [] (int a) const { return dat[a + offset]; } // get max r that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int max_right(const function f, int l = 0) { if (l == SIZE) return SIZE; l += offset; Monoid sum = IDENTITY; do { while (l % 2 == 0) l >>= 1; if (!f(F(sum, dat[l]))) { while (l < offset) { l = l * 2; if (f(F(sum, dat[l]))) { sum = F(sum, dat[l]); ++l; } } return l - offset; } sum = F(sum, dat[l]); ++l; } while ((l & -l) != l); // stop if l = 2^e return SIZE; } // get min l that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int min_left(const function f, int r = -1) { if (r == 0) return 0; if (r == -1) r = SIZE; r += offset; Monoid sum = IDENTITY; do { --r; while (r > 1 && (r % 2)) r >>= 1; if (!f(F(dat[r], sum))) { while (r < offset) { r = r * 2 + 1; if (f(F(dat[r], sum))) { sum = F(dat[r], sum); --r; } } return r + 1 - offset; } sum = F(dat[r], sum); } while ((r & -r) != r); return 0; } // debug friend ostream& operator << (ostream &s, const SegTree &seg) { for (int i = 0; i < seg.size(); ++i) { s << seg[i]; if (i != seg.size()-1) s << " "; } return s; } }; vector calc_divisor(long long n) { vector res; for (long long i = 1LL; i*i <= n; ++i) { if (n % i == 0) { res.push_back(i); long long j = n / i; if (j != i) res.push_back(j); } } sort(res.begin(), res.end()); return res; } template struct BIT { Abel UNITY_SUM = 0; vector dat[2]; // [0, n) BIT(int n, Abel unity = 0) : UNITY_SUM(unity) { init(n); } void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); } // [a, b), a and b are 0-indexed inline void sub_add(int p, int a, Abel x) { for (int i = a; i < (int)dat[p].size(); i |= i + 1) dat[p][i] = dat[p][i] + x; } inline void add(int a, int b, Abel x) { sub_add(0, a, x * (-a)); sub_add(1, a, x); sub_add(0, b, x * b); sub_add(1, b, x * (-1)); } // [a, b), a and b are 0-indexed inline Abel sub_sum(int p, int a) { Abel res = UNITY_SUM; for (int i = a - 1; i >= 0; i = (i & (i + 1)) - 1) res = res + dat[p][i]; return res; } inline Abel sum(int a, int b) { return sub_sum(0, b) + sub_sum(1, b) * b - sub_sum(0, a) - sub_sum(1, a) * a; } // debug void print() { for (int i = 0; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ","; cout << endl; } }; struct HopcroftKarp { int sizeL, sizeR; vector > list; // left to right // result vector seen, matched; vector level, matching; // base HopcroftKarp(int l, int r) : sizeL(l), sizeR(r), list(l, vector()) { } inline vector& operator [] (int i) { return list[i]; } inline void addedge(int from, int to) { list[from].push_back(to); } inline friend ostream& operator << (ostream& s, const HopcroftKarp& G) { s << endl; for (int i = 0; i < G.list.size(); ++i) { s << i << " : "; for (int j = 0; j < G.list[i].size(); ++j) { s << G.list[i][j]; if (j + 1 != G.list[i].size()) s << ", "; } s << endl; } return s; } // methods void hobfs() { queue que; for (int left = 0; left < sizeL; ++left) { level[left] = -1; if (!matched[left]) { que.push(left); level[left] = 0; } } level[sizeL] = sizeL; while (!que.empty()) { int left = que.front(); que.pop(); for (int i = 0; i < list[left].size(); ++i) { int right = list[left][i]; int next = matching[right]; if (level[next] == -1) { level[next] = level[left] + 1; que.push(next); } } } } bool hodfs(int left) { if (left == sizeL) return true; if (seen[left]) return false; seen[left] = true; for (int i = 0; i < list[left].size(); ++i) { int right = list[left][i]; int next = matching[right]; if (level[next] > level[left] && hodfs(next)) { matching[right] = left; return true; } } return false; } int solve() { seen.assign(sizeL, false); matched.assign(sizeL, false); level.assign(sizeL+1, -1); matching.assign(sizeR, sizeL); int res = 0; while (true) { hobfs(); seen.assign(sizeL, false); bool finished = true; for (int left = 0; left < sizeL; ++left) { if (!matched[left] && hodfs(left)) { matched[left] = true; ++res; finished = false; } } if (finished) break; } return res; } }; /* int main() { int N, M; cin >> N >> M; vector A(N), B(N), T(M), C(M); for (int i = 0; i < N; ++i) cin >> A[i]; for (int i = 0; i < N; ++i) cin >> B[i]; for (int j = 0; j < M; ++j) cin >> T[j] >> C[j]; HopcroftKarp G(N, M); for (int i = 0; i < N; ++i) } */ int main() { int N, K; cin >> N >> K; vector A(N*2), C(N*2); for (int i = 0; i < N; ++i) { cin >> A[i]; A[i+N] = A[i]; } for (int i = 0; i < N; ++i) { cin >> C[i]; C[i+N] = C[i]; } vector S(N*2+1, 0); for (int i = 0; i < N*2; ++i) S[i+1] = S[i] + A[i]; long long res = 0; for (int l = 0; l < N; ++l) { //cout << "-----------=" << endl; COUT(l); vector> st; for (int r = l; r < N*2 && r-l < N; ++r) { auto canmerge = [&](set add) -> bool { set se = st.back(); bool ex = false; for (auto v : se) for (auto v2 : add) if (abs(v - v2) <= K) ex = true; return ex; }; set add; add.insert(C[r]); //COUT(canmerge(add)); while (!st.empty() && canmerge(add)) { for (auto v : add) st.back().insert(v); add = st.back(); st.pop_back(); } st.push_back(add); //cout << r << ": " << st << endl; if (st.size() == 1) { res = max(res, S[r+1] - S[l]); } } } cout << res << endl; } /* vector dp(N*2+1, vector(N*2+2, vector(52, false))); vector pl(N*2+1, vector(N*2+2, vector(52, -1))); for (int l = 0; l < N*2; ++l) { dp[l][l+1][C[l]] = true; pl[l][l+1][C[l]] = l; } for (int b = 2; b <= N; ++b) { for (int l = 0; l < N*2 && l+b <= N*2; ++l) { int r = l + b; for (int c = 0; c <= 50; ++c) { for (int m = l+1; m < r; ++m) { if (!dp[l][m][c] && !dp[m][r][c]) continue; for (int c2 = max(0, c-K); c2 <= min(50, c+K); ++c2) { if (dp[l][m][c] && dp[m][r][c2]) dp[l][r][c] = true; if (dp[l][m][c2] && dp[m][r][c]) dp[l][r][c] = true; } } //if (dp[l][r][c]) cout << l << ", " << r << ", " << c << endl; } } } long long res = 0; for (int l = 0; l < N; ++l) { for (int r = l+1; r-l <= N && r <= N*2; ++r) { for (int c = 0; c <= 50; ++c) { if (dp[l][r][c]) { res = max(res, S[r] - S[l]); } } } } cout << res << endl; */