#include <bits/stdc++.h> using namespace std; #define int long long int solve() { int n, l; cin >> n >> l; vector <int> x(n), t(n); for (int i = 0; i < n; ++i) { cin >> x[i]; } for (int i = 0; i < n; ++i) { cin >> t[i]; } int ans = 0; int inf = 2e18; vector <vector <vector <int>>> dp(2, vector <vector <int>> (n + 1, vector <int> (n + 1, 2e18))); vector <vector <vector <int>>> last = dp; dp[0][0][0] = 0; int st = 0; for (int j = 0; j <= n; ++j) { for (int f = 0; f + j < n; ++f) { if (f == 0) { st = l; } else { st = x[n - f]; } dp[0][j + 1][f] = min(dp[0][j + 1][f], dp[1][j][f] + l - st + x[j]); dp[1][j][f + 1] = min(dp[1][j][f + 1], dp[1][j][f] + st - x[n - f - 1]); if (j == 0) { st = 0; } else { st = x[j - 1]; } dp[1][j][f + 1] = min(dp[1][j][f + 1], l - x[n - f - 1] + st + dp[0][j][f]); dp[0][j + 1][f] = min(dp[0][j + 1][f], x[j] - st + dp[0][j][f]); } } swap(last, dp); for (int i = 0; i <= n; ++i) { for (int j = 0; j <= n; ++j) { for (int f = 0; f + j < n; ++f) { if (last[0][j][f] != inf) { if (j == 0) { st = 0; } else { st = x[j - 1]; } if (x[j] - st + last[0][j][f] <= t[j]) { // cout << i << " " << j << " " << f << endl; dp[0][j + 1][f] = min(dp[0][j + 1][f], x[j] - st + last[0][j][f]); // cout << dp[0][j + 1][f] << endl; } int ind = n - 1 - f; // cout << i << " " << j << " " << f << endl; // cout << l << " " << x[ind] << " " << st << " " << last[0][j][f] << " " << t[ind] << endl; if (l - x[ind] + st + last[0][j][f] <= t[ind]) { dp[1][j][f + 1] = min(dp[1][j][f + 1], l - x[ind] + st + last[0][j][f]); } } if (last[1][j][f] != inf) { if (f == 0) { st = l; } else { st = x[n - f]; } if (last[1][j][f] + st - x[n - f - 1] <= t[n - f - 1]) { // cout << i << " " << " " << j << " " << f << endl; dp[1][j][f + 1] = min(dp[1][j][f + 1], last[1][j][f] + st - x[n - f - 1]); } if (last[1][j][f] + l - st + x[j] <= t[j]) { // cout << i << " " << " " << j << " " << f << endl; dp[0][j + 1][f] = min(dp[0][j + 1][f], last[1][j][f] + l - st + x[j]); } } } } for (int j = 0; j <= n; ++j) { for (int f = 0; f + j < n; ++f) { if (f == 0) { st = l; } else { st = x[n - f]; } dp[0][j + 1][f] = min(dp[0][j + 1][f], dp[1][j][f] + l - st + x[j]); dp[1][j][f + 1] = min(dp[1][j][f + 1], dp[1][j][f] + st - x[n - f - 1]); if (j == 0) { st = 0; } else { st = x[j - 1]; } dp[1][j][f + 1] = min(dp[1][j][f + 1], l - x[n - f - 1] + st + dp[0][j][f]); dp[0][j + 1][f] = min(dp[0][j + 1][f], x[j] - st + dp[0][j][f]); } } bool flag = false; for (int j = 0; j <= n; ++j) { for (int f = 0; f + j <= n; ++f) { if (dp[0][j][f] < inf || dp[1][j][f] < inf) { flag = true; } last[0][j][f] = inf; last[1][j][f] = inf; } } swap(last, dp); if (flag) { ans = i + 1; } else { break; } } return ans; } int add(int mask, int j) { return mask | (1LL << j); } int bad(int n, int l, vector <int> x, vector <int> t) { // int n; // cin >> n; // vector <int> x(n), t(n); // int l; // cin >> l; int ans = 0; // for (int i = 0; i < n; ++i) { // cin >> x[i]; // } // for (int i = 0; i < n; ++i) { // cin >> t[i]; // } vector <vector <int>> dp((1LL << n), vector <int> (n + 1, 2e18)); dp[0][n] = 0; for (int mask = 0; mask < (1LL << n); ++mask) { for (int j = 0; j < n; ++j) { if (dp[mask][j] != 2e18) { for (int i = 0; i < n; ++i) { int d = abs(x[i] - x[j]); d = min(d, l - d); if (((mask >> i) & 1) == 0 && dp[mask][j] + d <= t[i]) { dp[add(mask, i)][i] = min(dp[add(mask, i)][i], dp[mask][j] + d); } } ans = max(ans, (int)__builtin_popcount(mask)); } } if (dp[mask][n] != 2e18) { for (int i = 0; i < n; ++i) { int d = abs(x[i]); d = min(d, l - d); if (((mask >> i) & 1) == 0 && dp[mask][n] + d <= t[i]) { dp[add(mask, i)][i] = min(dp[add(mask, i)][i], dp[mask][n] + d); } } ans = max(ans, (int)__builtin_popcount(mask)); } } return ans; } mt19937 rnd(39); int get_int(int l, int r) { return uniform_int_distribution <int> (l, r)(rnd); } int n, l; vector <int> x, t; void init() { n = get_int(1, 10); l = get_int(2, 100); x.resize(n); t.resize(n); for (int i = 0; i < n; ++i) { x[i] = get_int(1, l - 1); t[i] = get_int(1, 100); } sort(x.begin(), x.end()); } signed main() { cin.tie(0); ios::sync_with_stdio(false); cout << solve() << '\n'; } /* 4 19 3 7 12 14 2 0 5 4 */