#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
* BOI 2022 - Uplifting Excursion (Vault)
*
* Key idea:
* 1. Greedy: take as many pieces as possible without "overshooting" L
* 2. Prove that optimal differs from greedy by at most 2M add/remove operations
* 3. Use DP over small range to find the best adjustment
*/
const ll NEG_INF = -1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int M;
ll L;
cin >> M >> L;
vector<ll> A(2 * M + 1); // A[i] = count of pieces with uplift (i - M)
ll totalUplift = 0; // uplift if we take everything
ll totalCount = 0; // count if we take everything
for (int i = 0; i <= 2 * M; i++) {
cin >> A[i];
int uplift = i - M; // actual uplift value
totalUplift += A[i] * uplift;
totalCount += A[i];
}
// Handle uplift 0 separately: always take all of them (they're free!)
ll zeroCount = A[M];
A[M] = 0;
// Greedy solution:
// If totalUplift >= L: take all negatives, prefix of positives
// If totalUplift < L: take all positives, prefix of negatives (by absolute value)
vector<ll> greedy(2 * M + 1, 0); // greedy[i] = how many pieces of uplift (i-M) we take
ll greedyUplift = 0;
ll greedyCount = zeroCount; // always take all zeros
if (totalUplift >= L) {
// Take all negative uplift pieces
for (int i = 0; i < M; i++) { // uplift = i - M < 0
greedy[i] = A[i];
greedyUplift += A[i] * (i - M);
greedyCount += A[i];
}
// Take prefix of positive uplift pieces (smallest first)
for (int i = M + 1; i <= 2 * M; i++) { // uplift = i - M > 0
int uplift = i - M;
// How many can we take without exceeding L?
if (greedyUplift >= L) break;
ll canTake = min(A[i], (L - greedyUplift - 1) / uplift + 1);
// Actually we want greedyUplift + canTake * uplift <= L... but we want max canTake
// such that greedyUplift + canTake * uplift <= L
// Wait, we want to NOT exceed L, so:
// greedyUplift + canTake * uplift <= L
// canTake <= (L - greedyUplift) / uplift
// But we also want to be as close to L as possible
// Let's just take as many as possible without going over L
ll maxTake = A[i];
if (greedyUplift + maxTake * uplift <= L) {
greedy[i] = maxTake;
greedyUplift += maxTake * uplift;
greedyCount += maxTake;
} else {
// Take floor((L - greedyUplift) / uplift) pieces
ll take = (L - greedyUplift) / uplift;
greedy[i] = take;
greedyUplift += take * uplift;
greedyCount += take;
}
}
} else {
// Take all positive uplift pieces
for (int i = M + 1; i <= 2 * M; i++) { // uplift = i - M > 0
greedy[i] = A[i];
greedyUplift += A[i] * (i - M);
greedyCount += A[i];
}
// Take prefix of negative uplift pieces (closest to 0 first, i.e., -1, -2, -3, ...)
for (int i = M - 1; i >= 0; i--) { // uplift = i - M < 0
int uplift = i - M; // negative
if (greedyUplift <= L) break;
ll canTake = A[i];
// We want greedyUplift + canTake * uplift >= L
// Since uplift < 0, adding pieces decreases greedyUplift
// We want to stay >= L
if (greedyUplift + canTake * uplift >= L) {
greedy[i] = canTake;
greedyUplift += canTake * uplift;
greedyCount += canTake;
} else {
// Take floor((greedyUplift - L) / (-uplift)) pieces
ll take = (greedyUplift - L) / (-uplift);
greedy[i] = take;
greedyUplift += take * uplift;
greedyCount += take;
}
}
}
// Now greedyUplift is in [L - M, L] or [L, L + M]
// We need to adjust by delta = L - greedyUplift
// The adjustment uses at most 2M operations total
ll delta = L - greedyUplift;
// DP: dp[d] = max net change in count to achieve uplift change of d
// d ranges from -2*M*M to +2*M*M theoretically, but we only need around delta
// Let's use offset: d + offset -> index
// We need d in range roughly [-2*M*M, 2*M*M] but actually much smaller
// Since we do at most 2M ops, each changing uplift by at most M,
// total change is at most 2*M*M
// But actually we only care about d = delta, which is in [-M, M]
// However during DP construction we might hit values in [-2*M*M, 2*M*M]
int maxDelta = 2 * M * M + M; // safe upper bound
int offset = maxDelta;
int dpSize = 2 * maxDelta + 1;
vector<ll> dp(dpSize, NEG_INF);
dp[offset] = 0; // 0 change in uplift, 0 change in count
// For each uplift value (except 0), update DP using sliding window deque
// This is a bounded knapsack: we can take between -canRemove and +canAdd items of each type
for (int i = 0; i <= 2 * M; i++) {
if (i == M) continue; // skip uplift 0
int uplift = i - M;
int step = abs(uplift);
// How many can we ADD? (pieces not in greedy, but available)
ll addLim = max(0LL, min((ll)M, A[i] - greedy[i]));
// How many can we REMOVE? (pieces in greedy)
ll remLim = max(0LL, min((ll)M, greedy[i]));
if (addLim == 0 && remLim == 0) continue;
// We want: dp_new[j] = max over t in [-remLim, addLim] of: dp[j - t*uplift] + t
//
// For each residue class r mod |uplift|, process separately.
// Within a class, let pos[k] = r + k*step be the k-th index.
//
// For uplift > 0: j - t*uplift = pos[k] - t*step = pos[k - t]
// So we want max of dp[pos[k']] + (k - k') for k' in [k - addLim, k + remLim]
// = k + max of (dp[pos[k']] - k') for k' in [k - addLim, k + remLim]
//
// For uplift < 0: j - t*uplift = pos[k] + t*step = pos[k + t]
// So we want max of dp[pos[k']] + (k' - k) for k' in [k - remLim, k + addLim]
// = -k + max of (dp[pos[k']] + k') for k' in [k - remLim, k + addLim]
vector<ll> newDp = dp;
for (int r = 0; r < step; r++) {
// Collect indices in this residue class
vector<int> pos;
for (int j = r; j < dpSize; j += step) {
pos.push_back(j);
}
int sz = pos.size();
if (sz == 0) continue;
// Prepare values array
vector<ll> val(sz);
for (int k = 0; k < sz; k++) {
val[k] = dp[pos[k]];
}
if (uplift > 0) {
// Window is [k - addLim, k + remLim]
// We want max of (val[k'] - k') over this window, then add k
// Transform: store val[k'] - k' in arr
vector<ll> arr(sz);
for (int k = 0; k < sz; k++) {
arr[k] = (val[k] == NEG_INF) ? NEG_INF : val[k] - k;
}
// Sliding window maximum with window [k - addLim, k + remLim]
// Window size = addLim + remLim + 1
deque<int> dq; // indices into arr
int left = 0; // left boundary of current window (inclusive)
for (int k = 0; k < sz; k++) {
int winLeft = k - (int)addLim;
int winRight = k + (int)remLim;
// Add all indices from left up to min(winRight, sz-1) to deque
while (left <= winRight && left < sz) {
if (arr[left] != NEG_INF) {
while (!dq.empty() && arr[dq.back()] <= arr[left]) {
dq.pop_back();
}
dq.push_back(left);
}
left++;
}
// Remove indices outside window [winLeft, winRight]
while (!dq.empty() && dq.front() < winLeft) {
dq.pop_front();
}
// Get maximum
if (!dq.empty()) {
newDp[pos[k]] = max(newDp[pos[k]], arr[dq.front()] + k);
}
}
} else {
// uplift < 0
// Window is [k - remLim, k + addLim]
// We want max of (val[k'] + k') over this window, then subtract k
vector<ll> arr(sz);
for (int k = 0; k < sz; k++) {
arr[k] = (val[k] == NEG_INF) ? NEG_INF : val[k] + k;
}
deque<int> dq;
int left = 0;
for (int k = 0; k < sz; k++) {
int winLeft = k - (int)remLim;
int winRight = k + (int)addLim;
while (left <= winRight && left < sz) {
if (arr[left] != NEG_INF) {
while (!dq.empty() && arr[dq.back()] <= arr[left]) {
dq.pop_back();
}
dq.push_back(left);
}
left++;
}
while (!dq.empty() && dq.front() < winLeft) {
dq.pop_front();
}
if (!dq.empty()) {
newDp[pos[k]] = max(newDp[pos[k]], arr[dq.front()] - k);
}
}
}
}
dp = newDp;
}
// Check if we can achieve delta
int targetIdx = offset + delta;
if (targetIdx < 0 || targetIdx >= dpSize || dp[targetIdx] == NEG_INF) {
cout << "impossible\n";
} else {
cout << greedyCount + dp[targetIdx] << "\n";
}
return 0;
}
