ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX(a,b) ((a)>(b)?(a):(b))
long long maxPack(vector<int>& Ps, int index, int target) {
if (index==(int)Ps.size()-1) {
return (Ps[index]<target)?Ps[index]:0;
}
if (target-Ps[index]<0) return maxPack(Ps,index+1,target);
return MAX(Ps[index]+maxPack(Ps,index+1,target-Ps[index]),maxPack(Ps,index+1,target));
}
int main()
{
int N;
vector<int> Ps;
long long P,S;
long long target;
long long total=0;
cin >> N;
for(int i=0; i<N; ++i){
cin >> P;
Ps.push_back(P);
total+=P;
}
cin >> S;
if(S==0) {
sort(Ps.begin(),Ps.end());
cout << Ps.front() << endl;
} else {
target = P-S;
cout << total-maxPack(Ps,0,target) << endl;
}
return 0;
}