#include<iostream> #include<string> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #define MAX_N 1010 int dp[MAX_N][MAX_N]; int a[MAX_N]; bool cmp(int a, int b) { return a > b; } int main() { int n; while (cin>>n) { if (n == 0)break; for (int i = 0; i < n; i++) { cin >> a[i]; } int m; cin >> m; if (m<5) { cout << m << endl; continue; } sort(a, a + n, cmp); memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 1; i <n; i++)//0是不能到达这个下标,1是可以到达这个下标 { for (int j = 0; j <=m-5; j++)//j代表的是买菜的价格之和 { if (dp[i - 1][j] == 1) { dp[i][j + a[i]] = 1; dp[i][j] = 1; } } } int ans=0; for (int i = m-5; i>=0; i--)//找到最接近余额5的值的下标 { if (dp[n-1][i]==1) { ans = i; break; } } cout << m - ans - a[0] << endl;//最接近余额5的值减去最贵的 } return 0; }