问题 F: 装物品

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：15 解决：4

题目描述

有n件物品，第i件物品的重量为Wi （整数）。 对于给定的整数 Wi  ， 请选择一些物品，使得拼出的重量不超过W  ，请问在此前提下能拼出的最大重量是多少？

输入

输入的第一行包含一个整数n，表示物品数量。 第二行包含n个整数w1,w2,w3...wn分别为每个物品的重量。 最后一行包含一个整数w。

输出

输出一行，包含一个整数，表示答案。

样例输入 复制 

3
4 4 6
12

样例输出 复制 

10

提示

对于30%的评测用例，1<=n<=20。 对于所有评测用例 1<=n<=100,1<=Wi<=1000,1<=W<=10000.