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+j] = arr[i] + arr[j]
			}
		}
		sort.Slice(sums, func(i, j int) bool { return sums[i] < sums[j] })

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

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 100000000
int sum[1000*1000];
int v[1000];
int n, m;

int main(){
    int n, m;
    while(cin >> n >> m, n||m){
        
        for(int i=0; i<n; ++i){
            int a; cin >> a;
            v[i] = a;
        }
        sort(v, v + n);
        
        int maxV=0;
        
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j){
                sum[i*n+j] = v[i]+v[j];
                //cout << sum[i*n+j] << end;
            }
        }
        sort(sum, sum+n*n);
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j){
                for(int i=0; i<=m-v[i]-v[j]; i++){
                    
                    if(v[i]+v[j]<=m) {
                        maxV=max(maxV,v[i]+v[j]+sum[upper_bound(sum,sum + n*n, m-v[i]-v[j])-sum-1]);
                    }
                }
            }
        }
        cout << maxV << endl;
    }
}

C++: #include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <string>
#define SIZE 1005
#define LSIZE 1000005
#define INF 1000000005LL

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int n;
ll M;
ll T[SIZE];
ll S[LSIZE];

ll solve()
{
	scanf("%d %lld",&n,&M);
	if(n+M ==0)return -1;
	for(int i=1;i<=n;i++)scanf("%lld",&T[i]);
	T[0]=0;
	for(int i=0;i<=n;i++){
		for(int j=i;j<=n;j++){
			S[i*(n+1)+j] = T[i]+T[j];
		}
	}
	ll maxv=0;
	ll v;
	sort(S,S+(n+1)*(n+1));
	for(int i=0;i<=n;i++){
		for(int j=i;j<=n;j++){
			if(T[i]+T[j]<=M){
				v = T[i]+T[j]+S[upper_bound(S,S+(n+1)*(n+1),M-T[i]-T[j])-S-1];
				maxv = max(maxv,v);
			}
		}
	}
	return maxv;
}

int main()
{
	while(1){
		ll ans = solve();
		if(ans==-1)break;
		else printf("%lld\n",ans);
	}
	return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i,l,n) for(int i=l;i<n;i++)
#define rer(i,l,n) for(int i=l;i<=n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int n,m,ans,MAX;
vi d(1010);

void solve(int sc,int k){
	if(sc>m) return;
	MAX=max(MAX,sc);
	if(k==4) return;
	rep(i,0,n+1){
		solve(sc+d[i],k+1);
	}
}

int main(){
	while(1){
		ans=0,MAX=0;
		cin>>n>>m;
		if(n==0 && m==0) break;
		d[0]=0;
		rep(i,1,n+1) cin>>d[i];
		sort(all(d));
		reverse(all(d));
		solve(0,0);
		o(MAX);
	}
}

C++: #include <cstdio>
#include <algorithm>
int a[1001],b[510001],*p;main(){
	int n,m,i,j,k,r;
	for(;scanf("%d%d",&n,&m)>1&&n;printf("%d\n",r)){
		for(i=1;i<=n;i++)scanf("%d",a+i);
		for(k=i=0;i<=n;i++)for(j=i;j<=n;j++)b[k++]=a[i]+a[j];
		std::sort(b,b+k);
		for(r=i=0;b[i]<=m&&i<k;i++){
			p=std::upper_bound(b,b+k,m-b[i]);
			if(p>b&&r<b[i]+*(p-1))r=b[i]+*(p-1);
		}
	}
}

C++: //JOI 2008??´???3??? ?????????

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>

using namespace std;

#define MAX -210000000
#define MIN 210000000

int a,b;
int d[1000],c[1000*1000+2],hk=0,mcunt,low,high;
int x,pr=0,flg[200000000],m,ff=0;

int main(){ 
	
	scanf("%d %d",&a,&b);
	
	d[0]=0;
	hk=0;
	for(int i=1;i<=a;i++) scanf("%d",&d[i]);
	
	for(int i=0;i<=a;i++){
		for(int j=0;j<=a;j++){
			if(flg[d[i]+d[j]]!=1){
				c[hk]=d[i]+d[j];
				//printf("%lld\n",c[cunt]);
				hk++;
				flg[d[i]+d[j]]=1;
			
			}
		}
	}
	//printf("Sort???\n");
	sort(c,c+hk);
	/*printf("\n");
	for(int i=0;i<hk;i++) printf("%d\n",c[i]);
	printf("\n");
	
	printf("hk=%d\n",hk);
	printf("c[low]=%d c[high]=%d\n",c[hk],c[hk-1]);*/
	                                 
	for(int i=0;i<hk;i++){
		x=b-c[i];
		//printf("x=%d\n",x);
		low=0;
		high=hk;
		
		while(low<=high){
			m=(low+high)/2;
			if(x==c[m]){
				ff=1;
				break;
			}
			if(x>c[m]) low=m+1;
			else if(x<c[m]) high=m-1;
		}
		//printf("\n%d\n",low);
		if(ff==1){
			pr=c[i]+c[m];
			break;
		}
		if(b>c[i]+c[high] && pr<c[i]+c[high]){
			pr=c[i]+c[high];
		//	printf("%d %d\n",c[i],c[high]);
		}
	}
	printf("%d\n",pr);
	return 0;
}

C++: #include <cstdio>
#include <algorithm>
int a[1001],b[500001],*p;main(){
	int n,m,i,j,k,r;
	for(;scanf("%d%d",&n,&m),n;printf("%d\n",r)){
		for(i=1;i<=n;i++)scanf("%d",a+i);
		for(k=i=0;i<=n;i++)for(j=i;j<=n;j++)b[k++]=a[i]+a[j];
		std::sort(b,b+k);
		for(r=i=0;i<k;i++){
			p=std::upper_bound(b,b+k,m-b[i]);
			if(p>b&&r<b[i]+*(p-1))r=b[i]+*(p-1);
		}
	}
}

C++: #include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define vi vector<int>
#define INF 999999999


template<class T>
T rev_lower_bound(vector<ll> vec,T num){
    ll left=0, right=vec.size()+1, mid=(left+right)/2LL;
    while(left+1<right){
        if(vec[mid]<=num) left = mid;
        else    right= mid;
        mid = (left+right)/2LL;
    }
    return mid;
}


int main(){
    
    int n,m;
    while(cin>>n>>m&&n&&m){
        vi p(n);
        rep(i,n)cin>>p[i];
        
        
        
        set<ll> val;
        val.insert(0);
        rep(i,n)val.insert(p[i]);
        rep(i,n)for(ll j=i;j<n;j++)val.insert(p[i]+p[j]);
        
        vector<ll> left,right;
        
        for(auto &v : val) left.pb(v);
        
        
        sort(all(left));
        right = left;
        
        ll maxi=0;
        rep(i,left.size()){
            ll num = left[i];
            if(num>m)continue;
            
            int pos = rev_lower_bound(right,m-num);
            
            maxi = max<ll>(maxi,num+right[pos]);
        }
        cout<<maxi<<endl;
    }
}

C++: #include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

typedef long long ll;

using namespace std;

int solve(int n,int m){
    bool dp[5][200000001]={0};
    int mato[1000];
    
    
    for(int i=0;i<n;i++)
        scanf("%d",&mato[i]);
    
    sort(mato,mato+n);
    
    for(int i=0;i<4;i++){
        for(int k=0;k<=m;k++){
            if(dp[i][k]){
                for(int j=0;mato[j]+k<=m;j++)
                    dp[i+1][k+mato[i]]=true;
    
                dp[i+1][k]=true;
            }
        }
    }
    
    for(int i=m;i>=0;i++)
        if(dp[4][i]){
            printf("%d\n",i);
            break;
        }
    
    return 0;
}

int main(){
    int n,m;
    
    while(1){
        scanf("%d%d",&n,&m);
        if(n+m==0)
            break;
        solve(n,m);
    }
    
    return 0;
}