#include<bits/stdc++.h> using namespace std; const int N=2000; int f[N][N],n,v[N],m=0; int main(){ cin>>n; for(int i=1;i<=n;i++){cin>>v[i];m+=v[i];} for(int i=1;i<=n;i++) for(int k=1;k<=min(i,n/2);k++) for(int j=v[i];j<=m/2;j++) f[j][k]=max(f[j][k],f[j-v[i]][k-1]+v[i]); cout<<f[m/2][n/2]; return 0; }