A. 徐老师的破烂背包

    传统题 文件IO:bag 1000ms 512MiB

徐老师的破烂背包

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

文件读写

本题使用文件输入输出,请在程序开头加入:

freopen("bag.in", "r", stdin);
freopen("bag.out", "w", stdout);

题目描述

徐老师收集完西瓜,决定给带一些给石老师分享

徐老师统计了自己摘到的 nn 个西瓜,其中第 ii 个西瓜的重量为 aia_i

现在徐老师准备选一些西瓜凑到重量恰好为 mm,然后装在他心爱的小背包里带给石老师

但是当徐老师背着西瓜找到石老师的时候,他发现他的背包居然破了!

于是徐老师急忙拿出背包里的西瓜检查,看看是否有西瓜丢失

现在徐老师想知道,从背包里拿出来的西瓜总重量可能有哪些情况?

P.S.1 如果某个原本装在背包里的西瓜丢失了,那么一定是这个西瓜整个丢失了,不会出现一个重量为 aia_i 的西瓜摔碎了丢了一部分这种情况

P.S.2 可能没有西瓜丢失,也有可能西瓜全丢了

输入格式

输入第一行包含两个整数 n,mn,m 含义如题

输入第二行包含 nn 个整数 aia_i,分别表示每个西瓜的重量

输出格式

输出一行包含若干个整数,表示背包里剩余西瓜可能的总重量,从小到大依次输出,中间用空格隔开

数据范围

测试点 数据范围
1∼31\sim 3 1≤n,m,ai≤81 \leq n,m,a_i \leq 8
4∼84\sim 8 1≤n,m,ai≤161 \leq n,m,a_i \leq 16
9∼129\sim 12 1≤n,m,ai≤501 \leq n,m,a_i \leq 50
13∼1613\sim 16 1≤n,m,ai≤1001 \leq n,m,a_i \leq 100
17∼2017\sim 20 1≤n,m,ai≤5001 \leq n,m,a_i \leq 500
5 8
4 3 4 4 1
0 1 3 4 5 7 8

样例解释1

若原本背包里的西瓜为 4,4{4,4},在找到石老师时剩余重量可能的情况为 0,4,8{0,4,8}

若原本背包里的西瓜为 1,3,4{1,3,4},在找到石老师时剩余重量可能的情况为 0,1,3,4,5,7,8{0,1,3,4,5,7,8}

综上,最终剩余的情况可能为 0,1,3,4,5,7,8{0,1,3,4,5,7,8}