Go: ///
// File:  0529.go
// Author: ymiyamoto
//
// Created on Wed Feb 28 20:39:28 2018
//
package main

import (
	"fmt"
	"sort"
)

func max(n, m int64) int64 {
	if n < m {
		return m
	} else {
		return n
	}
}

func main() {
	for {
		var N int
		var M int64
		fmt.Scan(&N, &M)
		if N == 0 && M == 0 {
			break
		}

		arr := make([]int64, N+1)
		for i := 1; i <= N; i++ {
			fmt.Scan(&arr[i])
		}
		sort.Slice(arr, func(i, j int) bool { return arr[i] < arr[j] })

		sums := make([]int64, len(arr)*len(arr))
		for i := 0; i < len(arr); i++ {
			for j := 0; j < len(arr); j++ {
				sums[i*len(arr)+j] = arr[i] + arr[j]
			}
		}

		sort.Slice(sums, func(i, j int) bool { return sums[i] < sums[j] })
		var m int64 = 0
		for _, val := range sums {
			rem := M - val
			if rem >= 0 {
				index := sort.Search(len(sums), func(i int) bool { return sums[i] > rem }) - 1
				if index >= 0 {
					m = max(m, val+sums[index])
				}
			}
		}
		fmt.Println(m)
	}
}

C++: #include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <map>
#include <set>
#include <stack>
#include <queue>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()
 
#define REP(i,s,e)	for(int i=(s); i<(e); i++)
#define rep(i,n)	REP(i,0,n)
#define REPE(i,s,e)	for(int i=s; i>e; i--)
#define repe(i,n)	REPE(i,n,-1)


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
typedef vector<vi> vvi;
 
const int IMAX=((1<<30)-1)*2+1;
const int INF=100000000;
const double EPS=1e-10;
//int mod=1000000007



const int MAX_N = 1000;
const int MAX_W = 200000000;

int dp[MAX_N + 1][MAX_W + 1][5];
int v[MAX_N], w[MAX_N];
int N,W;


int solve() {
	for(int i = 0; i < N; i++) {
		for(int j = 0; j <= W; j++){
			for(int k = 0; k < 5; k++){
				if(j < w[i] || k <1) {
					dp[i + 1][j][k] = dp[i][j][k];
				}
				else{
					dp[i + 1][j][k] = max(max(dp[i][j][k],dp[i][j-w[i]][k-1] + v[i]), dp[i + 1][j - w[i]][k-1] + v[i]);
				}
			}
		}
	}
	return dp[N][W][4];
}

int main(){
	int n, m;
	while(cin>>n>>m){
		N = n;
		W = m;
		for(int i = 0; i < n; i++){
			cin >> v[i];
			w[i] = v[i];
		}
		cout<<solve()<<endl;
	}
}

C++: #include <iostream>
using namespace std;
 
int main() {
	for(;;){
		/*入力*/
		int N,M,count=0;
		cin >> N >> M;
		if(N==0 && M==0)exit(0);
		int P[N+1],array[M+1]={0};
		P[0]=0;
		for(int i=1;i<=N;i++)cin >> P[i];
		for(int i=0;i<=N;i++)array[P[i]]=1;
 
		/*２投(０投１投を含む)で1からMまでが可能か判定*/
		for(int i=0;i<=N;i++){
			for(int j=0;j<=N;j++){
				if(P[i]+P[j] <= M)array[P[i]+P[j]]=1;
			}
		}
 
		/*４投に拡張*/
		for(int i=0;i<=M;i++){
			if(array[i]==1)count++;
		}
		int k=0,p[count];
		for(int i=0;i<=M;i++){
			if(array[i]==1){
				p[k]=i;
				k++;
			}
		}
		for(int i=0;i<count;i++){
			for(int j=0;j<count;j++){
				if(p[i]+p[j] <= M)array[p[i]+p[j]]=1;
			}
		}
 
		/*判定出力*/
		for(int i=M;i>0;i--){
			if(array[i]==1){
				cout << i << endl;
				break;
			}
		}
	}
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
	while(1){
	int n,m,p,q=0,r=0,l=0,s=0,e=0,ans=0;
	cin>>n>>m;
		if(n==0 && m==0)
			break;
	vector<int> a,x;
	a.push_back(0);
	for(int i=0;i<n;i++){
		cin>>p;
		a.push_back(p);
	}
	q=n+1;
	//cout<<q<<endl;
	for(int i=0;i<q;i++){
		for(int j=0;j<q;j++){
			x.push_back(a[i]+a[j]);
		}
	}
	sort(x.begin(),x.end());
	//for(int i=0;i<q*q;i++)
	//cout<<x[i]<<' ';
	//cout<<endl;
	for(int i=0;i<x.size();i++){
		r=m-x[i];
		//cout<<r<<"を探します"<<endl;
		if(r>=0){
			s=0;
			e=q*q;
			l=(s+e)/2;
			while(s<e){
				//cout<<"l="<<l<<endl;
				l=(s+e)/2;
				if(x[l]==r)break;
				if(x[l]>r){
					e=l-1;
				}else{
					s=l+1;
				}
			}
			while(x[l]>r&&p>0)
			l--;
			while(1){
				if(l+1==q*q)break;
				if(x[l+1]<=r)l++;
				else break;
			}
		ans=max(ans,x[i]+x[l]);
		}
	}
		cout<<ans<<endl;
	}
	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int main ( void )
{
	int n, m;
	int p[1000];
	set<int> S;
	
	while ( cin >> n >> m, (n | m) )
	{
		int ans = 0;
		S.clear();
		S.insert(0);
		for ( int i = 0; i < n; ++i )
		{
			cin >> p[i];
			for ( int j = 1; j <= 4; ++j )
			{
				if ( (p[i] * j) <= m )
				{
					S.insert(p[i]);
					ans = max( ans, (p[i] * j) );
				}
			}
		}
		
		for ( int i = 0; i < n; ++i )
		{
			for ( int j = i; j < n; ++j )
			{
				int x = p[i] + p[j];
				if ( x <= m )
				{
					S.insert(x);
					ans = max( ans, x );
					int y = m - x;
					while ( !S.count(y) && ( ans < (x + y) ) )
					{
						--y;
					}
					ans = max( ans, (x + y) );
				}
			}
		}
		
		if ( S.count(m) )
		{
			cout << "m=" << m << endl;
			continue;
		}
		
		cout << ans << endl;
	}
	
	return 0;
}

C++: #include <iostream>
#include <sstream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

typedef long long INT;
typedef vector <INT> VI;
typedef set <INT> SI;

INT solve( VI Q, INT M ) {
    INT answer = 0;
    int n = Q.size();
    for ( int i = 0; i < n; ++ i ) {
        int left = 0;
        int right = n;
        int m = M - Q[i];
        while ( left < right ) {
            int p = ( right - left) / 2 + left;
            if ( Q[p] <= m ) {
                answer = max( answer, Q[i] + Q[p] );
                left = p + 1;
            } else {
                right = p;
            }
        }
    }
    return answer;
}

int main() {
    int n, m;
    while ( cin >> n >> m ) {
        if ( n == 0 && m == 0 ) break;
        VI P( n );
        for ( int i = 0; i < n; ++ i ) {
            cin >> P[i];
        }
        SI Q_;
        Q_.insert( 0 );
        for ( int i = 0; i < n; ++ i ) {
            Q_.insert( P[i] > m ? 0 : P[i] );
            for ( int j = 0; j < n; ++ j ) {
                Q_.insert( ( P[i] + P[j] > m ? 0 : P[i] + P[j] ) );
            }
        }
        VI Q( Q_.begin(), Q_.end() );
        cout << solve( Q, m ) << endl;
    }
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(void){
	int n, m; cin >> n >> m;
	vector<int> p(n);
	rep(i, n) cin >> p[i];
	int ans = 0;
	rep(i, n)rep(j, n)rep(k, n)rep(l, n){
		int tmp = p[i] + p[j] + p[k] + p[l];
		if(tmp <= m) ans = max(ans, tmp);
	}
	printf("%d\n", ans);
	return 0;
}

C++: #include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
while(1){
int i,j,n,m,o=1,s=0;
static int p[1001]={0},up[1001*1001]={0};
scanf("%d%d",&n,&m);
if(n==0&&m==0)return 0;
for(i=1;i<=n;i++){
scanf("%d",&p[i]);
for(j=i;j>=0;j--){
up[o]=p[i]+p[j];
o++;
}
}
sort(up,up+o);
for(i=0;i<o;i++)printf("%d\n",up[i]);
for(i=0;i<o;i++){
if(up[i]+*(upper_bound(up,up+o,m-up[i])-1)<=m)s=max(s,up[i]+*(upper_bound(up,up+o,m-up[i])-1));
}
printf("%d\n",s);
}
return 0;
}