Type: Default 1000ms 256MiB

KKT基本算法背包问题

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

小明就要去春游了。妈妈给他买了很多好吃的。小明想把这些吃的都放进他的书包,但他很快发现,妈妈买的东西实在太多了,他必须放弃一些,但又希望能带尽可能多的好吃的。

已知小明的书包最多可以装人总重量为s的物品同时也知道小明妈妈给他买的每样东西的重量。请从这些好吃的中选出若干装入小明的书包中.使得装人物品的总重量正好为s。找到任意一组解输出即可。

Input Format

第1行包含两个正整数n(1<=n<=100)和s(1<=s<=10000)分别代表有n件物品和书包的最大承重s;

第2行包含n个正整数,代表每件物品的重量Wi(1<=Wi<=1000)。同行的两个数字之间用一个空格隔开。

Output Format

一行包含有若干用一个空格隔开的正整数,代表被放人书包的若干物品各自的重量。若无可行解,则输出"No Answer!"。

8 14
1 3 2 5 9 4 7 6

1 3 4 6
3 12
2 8 5

No Answer!