题目描述

题目译自 BalticOI $2022$ Day1「Uplifting Excursion」

有 $2m+1$ 种物品，重量分别为 $-m, -m+1, \ldots, m-1, m$。重量为 $i$ 的物品有 $a_i$ 个。

你需要拿走若干物品，使得这些物品重量之和恰好为 $L$。在此基础上，你需要拿尽可能多的物品。

问在物品重量之和恰好为 $L$ 的基础上，你最多能拿多少物品。

---

输入格式

第一行两个数 $m, L$。

第二行 $2m+1$ 个数，分别为 $a_{-m}, a_{-m+1}, \ldots, a_{m-1}, a_m$。

---

输出格式

一行一个数表示答案。若不存在方案，输出 impossible。

---

样例 1

输入

2 5
2 3 1 1 4

输出

9

一种方案是分别取 $[1,2,1,1,4]$ 个，重量之和为 $5$。总共取了 $9$ 个物品。

---

样例 2

输入

3 5
3 1 0 2 0 0 2

输出

impossible

可以证明不存在方案使得重量之和为 $5$。

---

样例 3

输入

1 5
0 0 6

输出

5

---

数据范围与提示

• 子任务 $1$ ($5$ 分)：$M, a_i \leq 50$
• 子任务 $2$ ($15$ 分)：$M, a_i \leq 100$
• 子任务 $3$ ($20$ 分)：$M \leq 30$
• 子任务 $4$ ($20$ 分)：$M \leq 50$
• 子任务 $5$ ($20$ 分)：$M \leq 100$
• 子任务 $6$ ($20$ 分)：没有特殊限制

对于子任务 $3$ 到子任务 $6$，如果通过 $\forall i<0, a_i=0$ 的测试点，可以获得一半的得分。

对于所有数据，满足：

• $1 \leq M \leq 300$
• $-10^{18} \le L \le 10^{18}$
• $0 \le a_i \le 10^{12}$

---

这个题目是一个带约束的子集和问题的变种，需要在重量和恰好为 $L$ 的前提下最大化物品数量。由于 $M$ 最大为 $300$，总物品种类为 $601$，但 $L$ 的范围极大（到 $10^{18}$），需要特殊的算法设计。