物品
题目描述
有 2m+1 种物品,重量依次为 −m,−m+1,…,m。重量为 i 的物品有 ai 个。
从这些物品中选择若干个,使总重量恰好为 L,并在此基础上使物品数量最多。允许一个也不选。
输入格式
第一行两个整数 m,L。
第二行 2m+1 个整数,依次为 a−m,a−m+1,…,am。
输出格式
有解时输出最多能选的物品数量,无解时输出小写 impossible。
样例 1 输入
2 5
2 3 1 1 4
样例 1 输出
9
样例 2 输入
3 5
3 1 0 2 0 0 2
样例 2 输出
impossible
样例 3 输入
1 5
0 0 6
样例 3 输出
5
样例说明
样例 1 按重量从 −2 到 2 分别选择 1,2,1,1,4 个,总重量为 −2−2+0+1+8=5,总数为 9。
数据范围
1≤m≤300,−1018≤L≤1018,0≤ai≤1012。
| 子任务 |
分值 |
附加限制 |
| 1 |
5 |
m,ai≤50 |
| 2 |
15 |
m,ai≤100 |
| 3 |
20 |
m≤30 |
| 4 |
m≤50 |
| 5 |
m≤100 |
| 6 |
无 |