饭卡

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。

Input多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。

n=0表示数据结束。
Output对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。Sample Input

1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0

Sample Output

-45
32


先减去5块钱，保留最贵的那个菜，看看剩下的钱充分消费的结果，最后再计算，如果余额本来就不够五元就直接输出。
注意先买便宜的，再买贵的，为了给五元这个界限，留下更大的空间。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define Max 1001
#define PI 3.1415927
using namespace std;
int n,price[Max],m;
int left()
{
    if(m < 5)return m;//啥也买不了
    int dp[Max] = {0};
    for(int i = 1;i < n;i ++)
    {
        for(int j = m - 5;j >= price[i];j --)//空出五元  看看剩下的钱 买前n个最多花多少钱
        {
            dp[j] = max(dp[j],dp[j - price[i]]+price[i]);
        }
    }
    return m - dp[m - 5] - price[n];//总钱数 减去花的最多的 再减去第n个
}
int main()
{
    while(cin>>n&&n)
    {
        for(int i = 1;i <= n;i ++)
        {
            cin>>price[i];
        }
        cin>>m;
        sort(price,price + n + 1);//先买便宜的，如果先买贵的可能买不了便宜的了。。但是便宜的剩的钱多就有更大可能性可以买贵的
        cout<<left()<<endl;
    }
}