#P10537. [2021年联测]物品

[2021年联测]物品

物品

题目描述

有 2m+12m+1 种物品,重量依次为 −m,−m+1,…,m-m,-m+1,\ldots,m。重量为 ii 的物品有 aia_i 个。

从这些物品中选择若干个,使总重量恰好为 LL,并在此基础上使物品数量最多。允许一个也不选。

输入格式

第一行两个整数 m,Lm,L。

第二行 2m+12m+1 个整数,依次为 a−m,a−m+1,…,ama_{-m},a_{-m+1},\ldots,a_m。

输出格式

有解时输出最多能选的物品数量,无解时输出小写 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 到 22 分别选择 1,2,1,1,41,2,1,1,4 个,总重量为 −2−2+0+1+8=5-2-2+0+1+8=5,总数为 99。

数据范围

1≤m≤3001\le m\le300,−1018≤L≤1018-10^{18}\le L\le10^{18},0≤ai≤10120\le a_i\le10^{12}。

子任务 分值 附加限制
1 5 m,ai≤50m,a_i\le50
2 15 m,ai≤100m,a_i\le100
3 20 m≤30m\le30
4 m≤50m\le50
5 m≤100m\le100
6 无