文理学院程序设计在线练习


Sky计划

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 280   Accepted Submission(s): 101
Problem Description

今天是Sky的生日,现在他要请朋友吃饭,计划好m(0<m<=20000)块钱用来买菜。已知共有n种(1<n<21)菜,价格分别为a1, a2,...,an。每种菜最多点一次。怎么完成Sky的计划最适合(把m块钱尽量用完)呢?现在请你给Sky编一个程序来解决这个问题。

Input

输入多组数据,一直处理到文件结束。第一行输入可能要买的菜种数n,第二行输入n种菜的价格,最后一行输入所计划好的钱m。

Output

对于输入的每组数据,都要有一行相应的输出,输出内容为完成Sky的计划所用去的最多的钱。

Sample Input
2
1 1
5
4
1 2 2 4
7
4
10 15 30 42
60
Sample Output
2
7
57
Author

njf