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 <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=a;i<b;++i)
#define for_rev(i,a,b) for(int i=a;i>=b;--i)
#define allof(a) a.begin(),a.end()
#define minit(a,b) memset(a,b,sizeof(a))
#define size_of(a) (int)a.size()

int N, M;
int p[1010];

int main() {
	while (cin >> N >> M, N) {
		for_(i,0,N) cin >> p[i];
	
		vector<int> vp;
		vp.push_back(0);
		for_(i,0,N) vp.push_back(p[i]);
	
		vector<int> sum2;
		for_(i,0,N + 1) for_(j,0,N + 1) sum2.push_back(vp[i] + vp[j]);
	
		sort(allof(sum2));
		int s_size = size_of(sum2);
		int ans = 0;
		for_(i,0,s_size) {
			int sum = sum2[i];
			if (sum <= M) {
				int sub = M - sum;
				int lb = *(upper_bound(allof(sum2), sub) - 1);
				//cout << sub << " " << lb << endl;
				sum += lb;
				ans = max(ans, sum);
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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

int n,m;
long long target[1000];
int sum = 0;

void chek(int cnt, int point,int now)
{
	int i;
	//int sum=0;
	sum = max(sum, point);
	if (cnt == 5)
	{
		return ;
	}
	if (sum == m)
	{
		return;
	}

	for (i = now; i <= n; i++)
	{
		if (point + target[i] <= m)
		{
			chek(cnt + 1, point + target[i],i);
		}
		else return;
	}

}

int main()
{
	//int sum;
	int i;

	while (scanf("%d %d",&n,&m), n != 0 || m != 0)
	{
		sum = 0;
		//printf("AA%d\n",m);
		for (i = 1; i <= n; i++)
		{
			scanf("%d", &target[i]);
		}

		sort(target + 1, target + n + 1);

		chek(1, 0,0);

		printf("%d\n", sum);
	}

	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std ;

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 1000000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

ll n,m;
vector<map<ll,bool>> dp(5);

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  while(cin >> n >> m && n && m){
    vary(ll,s,1001,0);
    rep(i,n){
      cin >> s[i];
    }
    sort(s.begin(),s.begin()+n);
    dp = vector<map<ll,bool>>(5);
    dp[0][0] = true;
    rep(i,4){
      for(auto &&e : dp[i]){
        if(e.fi > m) break;
        if(e.se){
          dp[i+1][e.fi] = true;
          rep(k,4){
            if(e.fi+s[k] <= m)
              dp[i+1][e.fi+s[k]] = true;
          }
        }
      }
    }
    for(auto rit = dp[4].rbegin(); rit != dp[4].rend(); ++rit){
      if(rit->se){
        cout << rit->fi << endl;
        break;
      }
    }
  }
  return 0;
}

C++: #include "stdio.h"
#include <iostream>
#include <algorithm>

using namespace std;

long long int gten[1000000];
long long int p[1111];

char bake[22222222];

long long int ans[1000];

int main()
{
  int ww = 0;
  while(1)
    {
      long long int n,m;
      scanf("%lld %lld",&n,&m);
      if(n == 0 && m == 0)
	{
	  break;
	}
      p[0] = 0;
      for(int i = 1; i <= n; i++)
	{
	  scanf("%lld",&(p[i]));
	}
      int nw = 0;
      for(int i = 0; i < 10; i++)
	{
	  for(int j = 0; j < 22222222; j++)
	    {
	      bake[j] = 0;
	    }
	  for(int j = 0; j <= n; j++)
	    {
	      for(int jj = 0; jj <= n; jj++)
		{
		  if(i * 22222222 <= p[j] + p[jj] && p[j] + p[jj] < (i + 1) * 22222222)
		    {
		      bake[p[j] + p[jj] - i * 22222222] = 1;
		    }
		}
	    }
	  for(int j = 0; j < 22222222; j++)
	    {
	      if(bake[j] == 1)
		{
		  gten[nw] = i * 22222222 + j;
		  nw++;
		}
	    }
	}
      long long int max = 0;
      int ai = 0;
      for(int i = nw - 1; i >= 0; i--)
	{
	  while(1)
	    {
	      if(ai + 1 >= nw)
		{
		  break;
		}
	      if(gten[i] + gten[ai + 1] <= m)
		{
		  ai++;
		  if(max < gten[i] + gten[ai])
		    {
		      max = gten[i] + gten[ai];
		    }
		}
	      else
		{
		  break;
		}
	    }
	}
      ans[ww] = max;
      ww++;
    }
  for(int i = 0; i < ww; i++)
    {
      printf("%lld\n",ans[i]);
    }
  return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<cstring>
#define INF 1<<28
using namespace std;

int p[1001];
int n;
int memo[10][1001];

int solve(int s, int m){

  if(s < 0) return INF;
  if(memo[m][s]) return memo[m][s];
  if(!m) return s;

  int res = INF;
  for(int i=0;i<=n;i++) res = min(res, solve(s-p[i], m-1));

  return memo[m][s] = res;
}

int main(){

  int s;
  while(true){
    cin >> n >> s;
    if(!n && !s) break;

    for(int i=1;i<=n;i++) cin >> p[i];

    memset(memo, 0, sizeof(memo));
    cout << s-solve(s, 4) << endl;

  }
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;

int main() {
	int n[1000], m[1000], p[10][1000],ans=0, i = 0;
	vector<int> v;
	while (cin >> n[i] >> m[i]) {
		if (n[i] == 0)break;
		for (int j = 0; j < n[i]; j++)cin >> p[i][j];
		i++;
	}
	for (int k = 0; k < i; k++) {
		ans = 0;
		v = vector<int>(1,0);
		for (int a = 0; a < n[k]; a++) {
			v.push_back(p[k][a]);
			for (int b = 0; b < n[k]; b++)
				v.push_back(p[k][a] + p[k][b]);
		}
		sort(v.begin(), v.end());
		for (int j = 0; j < v.size(); j++) {
			if (v[j] > m[k])break;
			decltype(v)::iterator itr= upper_bound(v.begin(), v.end(), m[k]-v[j]);
			itr--;
			ans = max(ans, v[j] + *itr);
		}
		cout << ans << endl;
	}
	return 0;
}