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 <bits/stdc++.h>

using namespace std;

// #define DEBUG

typedef long long ll;
typedef pair<int, int> p;
typedef pair<ll, int> lp;

const int NMAX = 1005;
const int MMAX = 2e8;

const ll INFLL = 1e18;
const int INF = 1e9;


ll N,M,K;
int A[NMAX] = {};
int dp[5][NMAX] = {};
std::vector<int> table;

int ans = 0;

int solve(){
  sort(A, A + N);
  for(int i = 0; i < N ; ++i) dp[1][i] = (A[i] <= M ? A[i] : 0);
  for (int k = 2; k <= 4; ++k)
  {
    for (int i = 0; i < N; ++i)
    {
      if (dp[k-1][i] + A[i] <= M)
      {
        dp[k][i] = dp[k-1][i] + A[i];
      }else{
        int* ite = upper_bound(A, A + i, M - dp[k-1][i]);
        if(ite != A) {
          dp[k][i] = dp[k-1][i] + *(--ite);
        }
        else {
          dp[k][i] = dp[k-1][i];
        }
      }
      if(i) dp[k][i] = max(dp[k][i-1], dp[k][i]);
    }
  }
  return dp[4][N-1];
}
int solve2(){
  table.clear();
  table.reserve((N+1)*(N+1));
  for (int i = 0; i < N + 1; ++i)
  {
    for (int j = 0; j < N + 1; ++j)
    {
      table.push_back(A[i] + A[j]);
    }
  }
  sort(table.begin(), table.end());

  ans = 0;
  for (int i = 0; i < (N + 1) * (N + 1); ++i)
  {
    int target = M - table[i];
    auto ite = upper_bound(table.begin(), table.end(), target);
    if (ite != table.begin())
    {
      ans = max(ans, table[i] + *(--ite));
    }
  }
  return ans;
}
void debug(){
  cout << "dp:\n";
  for (int i = 0; i < 4; ++i)
  {
    for (int j = 0; j < N; ++j)
    {
      cout << dp[i+1][j] << " ";
    }
    cout << endl;
  }
}

int main(int argc, char const *argv[])
{
  while(1) {
      cin >> N >> M;
      if(N == 0 && M == 0) break;
      memset(A, 0, sizeof(A));
      for (int i = 0; i < N; ++i)
      {
        scanf("%d", &A[i+1]);
      }
      cout << solve2() << endl;
      #ifdef DEBUG
      // debug();
      #endif
  }

  return 0;
}

C++: #include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int N,M;
int P[1111];
main(){
  while(1){
    scanf("%d %d",&N,&M);
    if(!N && !M) break;
    for(int i=0;i<N;i++){
      scanf("%d",&P[i]);
    }
    sort(P,P+N);
    int res=M;
    for(int i=0;i<4;i++){
      for(int i=N-1;i>-1;i--){
	if(M>=P[i]){
	  M-=P[i];
	  break;
	}
      }
    }
    printf("%d\n",res-M);
  }
}

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

using namespace std;

// #define DEBUG

typedef long long ll;
typedef pair<int, int> p;
typedef pair<ll, int> lp;

const int NMAX = 1005;
const int MMAX = 2e8;

const ll INFLL = 1e18;
const int INF = 1e9;


ll N,M,K;
int A[NMAX];
int dp[5][NMAX] = {};

int solve(){
  sort(A, A + N);
  for(int i = 0; i < N ; ++i) dp[1][i] = (A[i] <= M ? A[i] : 0);
  for (int k = 2; k <= 4; ++k)
  {
    for (int i = 0; i < N; ++i)
    {
      if (dp[k-1][i] + A[i] <= M)
      {
        dp[k][i] = dp[k-1][i] + A[i];
      }else{
        int* ite = upper_bound(A, A + i, M - dp[k-1][i]);
        if(ite != A) {
          dp[k][i] = dp[k-1][i] + *(--ite);
        }
        else {
          dp[k][i] = dp[k-1][i];
        }
      }
      if(i) dp[k][i] = max(dp[k][i-1], dp[k][i]);
    }
  }
  return dp[4][N-1];
}
void debug(){
  cout << "dp:\n";
  for (int i = 0; i < 4; ++i)
  {
    for (int j = 0; j < N; ++j)
    {
      cout << dp[i+1][j] << " ";
    }
    cout << endl;
  }
}

int main(int argc, char const *argv[])
{
  while(1) {
      cin >> N >> M;
      if(N == 0 && M == 0) break;
      memset(A, 0, sizeof(A));
      for (int i = 0; i < N; ++i)
      {
        scanf("%d", &A[i]);
      }
      cout << solve() << endl;
      #ifdef DEBUG
      debug();
      #endif
  }

  return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> a;
vector <int> all;
int n,m;



int bainary_search(int i) {
  int L=0;int R = all.size()-1,M;
  
  while(L<R) {
    M = (L+R)/2;
    if(all[i]+all[M] > m) R = M;
    else L = M+1;
  }
  if(L != 0)L--;
  return L;
}

int main() {

  while(1) {
    cin >> n >> m;
    if(n == 0 && m ==0) break;
    a.resize(n);
    for(int i=0;i<n;i++) cin >>a[i];

    a.push_back(0);
    all.clear();
    for(int i=0;i<a.size();i++) 
      for(int j=i;j<a.size();j++)
	all.push_back(a[i]+a[j]);

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

    int ans = 0;
    int allsize = all.size();
    for(int i=0;i<allsize;i++) {
      if(i!=allsize-1 && all[i] == all[i+1]) continue;
      int res = all[i] + all[bainary_search(i)];
      if(ans < res && res<= m) ans = res;
    }
    cout << ans <<endl;
  }
  return 0;
  
}

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

int main()
{
    for(;;){
        int n, m;
        cin >> n >> m;
        if(n == 0)
            return 0;

        vector<set<int> > num(5);
        num[0].insert(0);
        int ret = 0;
        for(int i=0; i<n; ++i){
            int a;
            cin >> a;
            for(int i=0; i<4; ++i){
                set<int>::iterator it;
                for(it=num[i].begin(); it!=num[i].end(); ++it){
                    int b = (*it) + a;
                    if(b <= m){
                        num[i+1].insert(b);
                        ret = max(ret, b);
                    }
                }
            }
        }
        cout << ret << endl;
    }
}