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 <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(int i, int j, int k){
// 	if(dp[i][j][k] != -1) return dp[i][j][k];
// 	int ret = 0;
// 	if(i == N) ret = 0;
// 	else if(j < w[i] || k == 4) ret =dp[i][j][k];
// 	else ret =max(max(solve(i,j,k),solve(i,j-w[i],k+1) + v[i]),solve(i+1,j-w[i],k + 1) + v[i]);
// 	return dp[i][j][k] = ret;
// }

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++){
		// 	for(int j = 0; j <=W; j++){
		// 		for(int k = 0; k < 4; k++){
		// 			dp[i][j][k] = -1;
		// 		}
		// 	}
		// }
		for(int i = 0; i < n; i++){
			cin >> v[i];
			w[i] = v[i];
		}
		cout<<solve()<<endl;
	}
}

C++: #include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
using namespace std;

long modpow(long a, long n, long mod) {
    long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod を計算する
long modinv(long a, long mod) {
    return modpow(a, mod - 2, mod);
}

int main()
{
    int P[1005];
    int sum1[1002005], sum2[1002005];
    int N;
    int M;

    for(;;){
        cin >> N >> M;
        //cout << N << " " << M << endl;
        if(N == 0 && M == 0)
            break;
        P[0] = 0;
        REP(i, N)
            cin >> P[i + 1];
        sort(P, P + N + 1);
        REP(i, N + 1)
            REP(j, N + 1){
                sum1[i * (N + 1) + j] = P[i] + P[j];
                sum2[i * (N + 1) + j] = M - P[i] - P[j];
            }
        sort(sum1, sum1 + (N + 1) * (N + 1));
        sort(sum2, sum2 + (N + 1) * (N + 1));
        long ans = 0;
        REP(i, (N + 1) * (N + 1)){
            int temp = (int)(lower_bound(sum2, sum2 + (N + 1) * (N + 1), sum1[i]) - sum2);
            //cout << N << " " << M << " " << sum1[i] << " " << sum2[temp] << endl; 
            if(temp != (N + 1) * (N + 1) && ans < (long)sum1[i] + (long)M - (long)sum2[temp] && M >= (long)sum1[i] + (long)M - (long)sum2[temp])
                ans = (long)sum1[i] + (long)M - (long)sum2[temp];
        }
        cout << ans << endl;
    }

    return 0;
}

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

using namespace std;

int main(){
	while(true){
		int n, m;
		cin >> n >> m;
		if(n == 0 && m == 0){ break; }
		vector<int> p(1, 0);
		for(int i = 0; i < n; i++){
			int val;
			cin >> val;
			p.push_back(val);
		}
		vector<int> p2;
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= i; j++){
				if(p[i] + p[j] <= m){ p2.push_back(p[i] + p[j]); }
			}
		}
		sort(p2.begin(), p2.end());
		int answer = 0;
		for(int i = 0; i < p2.size(); i++){
			vector<int>::iterator it = upper_bound(p2.begin(), p2.end(), m - p2[i]);
			int v = p2[i] + *(--it);
			answer = max(answer, v);
		}
		cout << answer << endl;
	}
	return 0;
}

C++: #include <set>
#include <algorithm>
#include <iostream>
#define MAX(a,b) (((a)>(b))?(a):(b))
using namespace std;
typedef long long int lli;

set<lli> v;
lli m,n;
lli k;
int mx;

int dfs(int num,int score){
	mx=MAX(mx,score);
	if(num<4){
		for(set<lli>::iterator it=v.begin();it!=v.end()&&score+*it<=m;it++){
			dfs(num+1,score+*it);
		}
	}
	return mx;
}

int main(void){
	while(cin>>n>>m,(n||m)){
		v.clear();
		mx=0;
		for(lli i=0;i<n;i++){
			cin>>k;
			v.insert(k);
		}
		for(set<lli>::iterator itm=v.begin();itm!=v.end();itm++){
			dfs(1,*itm);
		}
		cout<<mx<<endl;
	}
	return 0;
}

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

#define MAX_N (1000)
#define MAX_M (2 * 1e8)

using namespace std;

int field[MAX_N + 1];
int fld[(MAX_N + 1) * (MAX_N + 1)];

int N,M;

int ans;

int bin_search(int tar,int *s,int *e){
	int result;
	int width = e - s;
	while(true){
		width = e - s;
		if(width <= 1){
			result = *s;
			break;
		}

		if(*(s + (width / 2)) <= tar){
			s = s + (width / 2);
		}
		else{
			e = s + (width / 2);
		}
	}
	
	return result;
}

void solve(){
	for(int i = 0;i <= N;i++){
		for(int j = 0;j <= N;j++){
			fld[(N + 1) * i + j] = field[i] + field[j];
		}
	}

	sort(fld,fld + (N + 1) * (N + 1));

	ans = 0;
	int rest;
	int sample;
	for(int i = 0;i <= N;i++){
		for(int j = 0;j <= N;j++){
			rest = M - (field[i] + field[j]);
			if(rest < 0) break;
			sample = bin_search(rest,fld,fld + (N + 1) * (N + 1));
			ans = max(ans,field[i] + field[j] + sample);
		}
	}

	return ;
}

int main(){

	while(true){
		scanf("%d%d",&N,&M);
		if(N == 0 && M == 0) break;
		for(int i = 1;i <= N;i++){	//fiest element is 0;
			scanf("%d",field + i);
		}

		solve();

		printf("%d\n",ans);

	}

	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
  int N, M;
  int P[10001];

  while(cin >> N >> M){
    if(N == 0 && M == 0) break;
    
    for(int i = 0 ; i < N ; i++){
      cin >> P[i];
    }
    
    sort(P, P+N, greater<int>());
    int ans = 0;
    
    for(int i = 0 ; i < N ; i++){
      if(M < 0) break;
      if(M >= P[i]){
	ans += (M / P[i]) * P[i];
	M -= (M / P[i]) * P[i];
      }
    }
    cout << ans << endl;
  }
  return 0;
}

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