1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 int max(int a,int b)
 7 {
 8     return a>b?a:b;
 9 }
10 int main()
11 {
12     int i,j,n,m;
13     int a[1005],dp[1005];
14     while(~scanf("%d",&n)&&n)
15     {
16         for(i=0; i<n; i++)
17             scanf("%d",&a[i]);
18         scanf("%d",&m);
19         sort(a,a+n);   //排序，找到最贵的菜
20         if(m<5)  //假如饭卡初始金额不足5元，则无法购买任何物品
21         {
22             printf("%d\n",m);
23             continue;
24         }
25         memset(dp,0,sizeof(dp));
26         for(i=0; i<n-1; i++)   //m-5块钱在n-1个物品内最多买多少钱的菜
27             for(j=m-5; j>=a[i]; j--)
28                 dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
29         printf("%d\n",m-dp[m-5]-a[n-1]);  //计算最少剩余的钱
30     }
31     return 0;
32 }