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

import (
	"fmt"
	"sort"
)

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

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

		arr := make([]int, N+1)
		for i := 1; i <= N; i++ {
			fmt.Scan(&arr[i])
		}
		sort.Ints(arr)

		sums := make([]int, 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.Ints(sums)

		m := 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<algorithm>
#include<cmath>
#include<vector>
#include<climits>

using namespace std;

int main() {
	long long   m[10], t[10][1000]{ 0 }, a[1000];
	int n[10], i = 0;
	while (1) {
		cin >> n[i] >> m[i];
		if (n[i] == 0)break;
		for (int j = 0; j < n[i]; j++)cin >> t[i][j];
		i++;
	}
	for (int k = 0; k < i; k++) {
		long long ans = 0;
		for (int j = 0; j < n[k]; j++)a[j] = t[k][j];
		sort(a, a + n[k]);
		for (int p = n[k] - 1; p >= 0; p--) {
			if (a[p] > m[k])continue;
			else if (a[p] == m[k]) {
				ans = m[k];
				goto ANS;
			}
			else if (ans > a[p] * 4)goto ANS;
			else {
				ans = max(ans, a[p]);
				for (int q = p; q >= 0; q--) {
					if (a[p] + a[q] > m[k])continue;
					else if (a[p] + a[q] == m[k]) {
						ans = m[k];
						goto ANS;
					}
					else if (ans > a[p] + a[q] * 3)goto ANS;
					else {
						ans = max(ans, a[p] + a[q]);
						for (int r = q; r >= 0; r--) {
							if (a[p] + a[q] + a[r] > m[k])continue;
							else if (a[p] + a[q] + a[r] == m[k]) {
								ans = m[k];
								goto ANS;
							}
							else if (ans > a[p] + a[q] + a[r] * 2)goto ANS;
							else {
								ans = max(ans, a[p] + a[q] + a[r]);
								for (int s = r; s >= 0; s--) {
									if (a[p] + a[q] + a[r] + a[s] > m[k])continue;
									else if (a[p] + a[q] + a[r] + a[s] == m[k]) {
										ans = m[k];
										goto ANS;
									}
									else if (ans > a[p] + a[q] + a[r] + a[s])break;
									else ans = max(ans, a[p] + a[q] + a[r] + a[s]);
								}
							}
						}
					}
				}
			}
		}
	ANS:
		cout << ans << endl;
	}
	return 0;
}

C++: #include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int N, M;



int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M;
	while (N) {
		int num[1001];
		int ans = 0;
		set<int>F;
		set<int>S;
		for (int i = 0; i < N; i++)cin >> num[i];
		F.insert(0);
		for (int i = 0; i < N/2; i++) {
			F.insert(num[i]);
			for (int j = 0; j < N/2; j++) {
				F.insert(num[i] + num[j]);
			}
		}
		S.insert(0);
		for (int i = N/2; i < N; i++) {
			S.insert(num[i]);
			for (int j = N/2; j < N; j++) {
				S.insert(num[i] + num[j]);
			}
		}
		set<int>::reverse_iterator ritr = S.rbegin();
		for (auto i : F) {
			if (ritr == S.rend())break;
			while ((i + *ritr) > M) {
				++ritr;
				if (ritr ==S.rend())break;
			}
			if(ritr!=S.rend())	ans = max(ans, i + *ritr);
		}
		cout << ans << endl;
		cin >> N >> M;
	}
	return 0;
}

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

using namespace std;

int N;
int M;
int P[1000];
int ans=0;

void func(int n,int dart,int sum){
    ans=max(ans,sum);
    if(dart==4 || n<0)return ;
    
    
    if(sum+P[n]<=M){
        func(n-1,dart+1,sum+P[n]);
        func(n,1+dart,sum+P[n]);
        func(n-1,dart,sum);
    }
    else func(--n,dart,sum);
    
    return ;
}
int main(){
    while(cin>>N>>M,N,M){
        for(int i=0;i<N;i++){
            cin>>P[i];
        }
        sort(P,P+N);
        func(N-1,0,0);
        cout<<ans<<endl;
        ans=0;
    }
    
    
}

C++: #include <bits/stdc++.h>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;
const double PI = acos(-1.0);
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
using ll = long long int;
using P = pair<int, int>;
using edge = struct
{
    int to;
    int cost;
};

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    int N, M;
    while (cin >> N >> M && N)
    {
        vector<int> P(N + 1);
        P[0] = 0;
        rep(i, N) cin >> P[i + 1];

        vector<ll> candi;

        rep(i, N + 1)
        {
            for (int j = i + 1; j <= N; j++)
            {
                candi.push_back(P[i] + P[j]);
            }
        }

        sort(candi.begin(), candi.end());

        ll ans = 0;

        rep(i, candi.size())
        {
            ll diff = M - candi[i];

            if (diff < 0) break;

            int l = 0, r = candi.size();

            auto itr = upper_bound(candi.begin(), candi.end(), diff);

            ans = max(ans, (M >= candi[i] + *(itr - 1) ? candi[i] + *(itr - 1) : 0));
        }

        cout << ans << endl;
    }

    return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;

int main(){
	int N,M;
	while(cin>>N>>M,N||M){
		int dp[2][5][5]={},P,ans=0;
		for(int i=0;i<N;i++){
			cin>>P;
			for(int j=0;j<=4;j++){
				for(int k=0;k<=4;k++){
					for(int l=0;j+l<=4 && dp[i&1][j][k]+P*l<=M;l++){
						dp[(i+1)&1][j+l][l] = max(dp[(i+1)&1][j+l][l],dp[i&1][j][k]+P*l);
						ans=max(ans,dp[i&1][j][k]+P*l);
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

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

int main(){
  int n, m;
  while(1){
    scanf("%d%d", &n, &m);
    if(n == 0 && m == 0)return 0;
    int res = 0, tmp;
    vector<int> points, points2;
    for(int i = 0;i < n;i++){
      scanf("%d", &tmp);
      points.push_back(tmp);
    }
    vector<int>::iterator it1,it2;
    for(it1 = points.begin();it1 != points.end();it1++){
      for(it2 = points.begin();it2 != points.end();it2++){
	points2.push_back(*it1 + *it2);
      }
    }
    sort(points2.begin(),points2.end());
    for(it1 = points2.begin();it1 != points2.end();it1++){
      it2 = upper_bound(points2.begin(), points2.end(), m - *it1);
      if(it2 == points2.begin())continue;
      it2--;
      res = max(res, *it1 + *it2);
    }
    printf("%d\n",res);
  }
}

C++: #include <cstdio>
#include <algorithm>
using namespace std;

#define MAX_N 1000
int P[MAX_N + 1];
int N, M;
int table[5][MAX_N + 1];

int dfs(int a, int b, int c){
	if(c > M) return P[b] * -1;
	if(a == 0) return P[b];
	if(table[a][b] >= 0) return table[a][b];
	
	int cho = b;
	while(cho <= N){
		int d = dfs(a - 1, cho, c + P[b]) + P[b];
		table[a][b] = max(table[a][b], (d > M)? 0 : d);
		cho++;
	}
	
	return table[a][b];
}

int main(){
	while(1){
		for(int i = 0; i < 5; i++){
			for(int j = 0; j <= MAX_N; j++){
				table[i][j] = -1;
			}
		}
		
		scanf("%d%d", &N, &M);
		
		if(N == 0 && M == 0) return 0;
		
		P[0] = 0;
		for(int i = 1; i <= N; i++) scanf("%d", &P[i]);
		
		printf("%d\n", dfs(4, 0, 0));
	}
}