1 /*
 2 Author:    Leo.W
 3 Descriptipn:    飯卡小于5元時無法刷卡，但不小于五元時可以刷到爆，k種食物，一種一次，求飯卡最少可以剩多少。    
 4 How to Do:    DP動態(tài)規(guī)劃，狀態(tài)轉(zhuǎn)移類似0-1背包問題，先把所有物品排序，找出最貴食物max。對其他食物進行0-1背包，
 5             找出其中最接近卡中余額m-5的最大值m',則結(jié)果即為m-m'-max.
 6   */
 7 #include <iostream>
 8 #include <string.h>
 9 #include <algorithm>
10 using namespace std;
11 #define max(a,b) (a)>(b)?(a):(b)
12 int d[1002];
13 int dp[1002];
14 int main(){
15     //freopen("in.txt","r",stdin);
16     int n;
17     while (scanf("%d",&n)&&n){
18         int i,j;
19         for(i=0;i<n;i++)    scanf("%d",&d[i]);
20         sort(d,d+n);
21         int maxs=d[n-1];
22         int m;
23         scanf("%d",&m);
24         if(m>=5){//此處WA了一次，要細致啊！！
25             memset(dp,0,sizeof(dp));
26             for(i=0;i<n-1;i++){
27                 for(j=m-5;j>=d[i];j--){
28                     dp[j]=max(dp[j],dp[j-d[i]]+d[i]);
29                 }
30             }
31             printf("%d\n",m-dp[m-5]-maxs);
32         }
33         else
34             printf("%d\n",m);
35     }
36     return 0;
37 }
38