Problem:


ダーツ  

問題

あなたは以下のルールでダーツゲームをすることになった.

あなたは,矢を的(まと)に向かって 4 本まで投げることができる.必ずしも 4 本全てを投げる必要はなく,1 本も投げなくてもかまわない.的は N 個の部分に区切られていて,各々の部分に点数 P1,..., PN が書か   れている.矢が刺さった場所の点数の合計 S があなたの得点の基礎となる.S があらかじめ決められたある点数 M 以下の場合は S がそのままあなたの得点となる.しかし,S が M を超えた場合はあなたの得点は 0 点となる.

的に書かれている点数と M の値が与えられたとき,あなたが得ることのできる点数の最大値を求めるプログラムを作成せよ.

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

1 行目には,整数 N (1 ≤ N ≤ 1000) と M (1 ≤ M ≤ 200000000 = 2 &times; 108)がこの順に空白区切りで書かれている.2 行目以降の第 1 + i 行目 (1 ≤  i ≤ N ) には, Pi (1 ≤ Pi ≤ 100000000 = 108 ) が書かれている.

採点用データのうち, 配点の 20% 分は N ≤   100 を満たし,配点の 50% 分はN ≤ 300 を満たす.

N, M がともに 0 のとき入力の終了を示す. データセットの数は 10 を超えない．

出力

データセットごとにあなたが得ることのできる点数の最大値を１行に出力する.

入出力例

入力例

4 50
3
14
15
9
3 21
16
11
2
0 0

出力例

48
20

1つ目の例では,15 点の部分に 3 本,3 点の部分に 1 本の矢が刺さった場合にあなたの得点は最大になり,その得点は 48 点である.

2つ目の例では,16 点の場所に 1 本,2 点の場所に 2 本の矢が刺さった場合にあなたの得点は最大になり,その得点は 20 点である.

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
4 50
3
14
15
9
3 21
16
11
2
0 0


Sample output:
48
20

Submission status: Wrong Answer

Solution code:
import bisect

while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    a=[0 for x in range(N+1)]
    for i in range(N):
        a[i+1]=int(raw_input())
    #b=sorted([x+y for x in a for y in a])
    #c=[]
    #for i in range(1,len(b)):
    #    if b[i]>M:
    #        break
    #    elif b[i-1]!=b[i]:
    #        c.append(b[i-1])
    b=[a[x]+a[y] for x in range(N+1) for y in range(x,N+1)]
    #c=f7(b)
    c=sorted(b)
    largest=0
    id=0
    st=bisect.bisect(c,M)
    for i in range(st,len(c)+1):
        if id==len(c):
            break
        while(id<len(c) and c[-i]+c[id]<=M):
            largest=max(largest,c[-i]+c[id])
            id+=1
    print largest

Submission status: Wrong Answer

Solution code:
while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    p=[int(raw_input()) for _ in xrange(n)]
    dp=[[0]*5 for _ in xrange(n+1)]
    for i in xrange(n):
        for j in xrange(1,5):
            for k in xrange(1,5):
                if j<k:
                    continue
                else:
                    if dp[i][j-k]+k*p[i]>m:continue
                    dp[i+1][j]=max(dp[i][j],dp[i+1][j],dp[i][j-k]+k*p[i])
    print(max(dp[n]))

Submission status: Wrong Answer

Solution code:
import bisect
def main():
	while True:
		n,m=map(int,input().split())
		if n==0 and m==0:
			break
		p=list()
		for i in range(n):
			p.append(int(input()))
		p.append(0)
		st=set()
		for i in p:
			for j in p:
				if i+j<=m:
					st.add(i+j)
		ls=list(st)
		ans=0
		for x in ls:
			idx=bisect.bisect_right(ls,m-x)
			idx-=1
			ans=max(ans,x+ls[idx])

		print(ans)

if __name__=="__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
while True :
	n,m = map(int,raw_input().split())
	if n == 0 and m == 0 :
		break

	else :
		arr = []
		arr.append(0)
		for i in range(n):
			arr.append(int(input()))

		for i in range(n+1):
			for j in range(n+1):
				arr.append(arr[i] + arr[j])

		arr.sort()
		ans = 0
		for i in arr :
			if i > m : 
				break

			a = bisect.bisect_left(arr,m-i)-1
			ans = max(ans,i+arr[a] if i+arr[a] <= m else 0)

		print ans

Submission status: Time Limit Exceeded

Solution code:
import bisect
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    if N*M == 0:
        return False
    P = [0]+[int(input()) for _ in range(N)]
    # solve
    k = [p1+p2 for p1, p2 in zip(P, P)]
    k = sorted(k)

    ret = 0
    for i in range(N):
        for j in range(N):
            tmp = P[i]+P[j]
            if tmp > M:
                continue
            else:
                r = M-tmp
                l = bisect.bisect_right(k, r)
                if l >= len(k):
                    tmp += k[-1]
                elif l != 0:
                    tmp += k[l-1]
            ret = max(ret, tmp)
    return ret


ans = []
while True:
    ret = solve()
    if ret:
        ans.append(ret)
    else:
        break
print("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    a=[0]
    for i in range(N):
        a.append(int(raw_input()))
    b=sorted([x+y for x in a for y in a])
    c=[]
    for i in range(1,len(b)):
        if b[i]>M:
            break
        elif b[i-1]!=b[i]:
            c.append(b[i-1])
    largest=c[-1]
    id=0
    for i in range(1,len(c)+1):
        if id==len(c):
            break
        while(id<len(c) and c[-i]+c[id]<=M):
                #print c[-i],c[id],c[-i]+c[id]
                largest=max(largest,c[-i]+c[id])
                id+=1
    print largest

Submission status: Time Limit Exceeded

Solution code:
def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]


while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    a=[0]
    for i in range(N):
        a.append(int(raw_input()))
    #b=sorted([x+y for x in a for y in a])
    #c=[]
    #for i in range(1,len(b)):
    #    if b[i]>M:
    #        break
    #    elif b[i-1]!=b[i]:
    #        c.append(b[i-1])
    b=[x+y for x in a for y in a]
    c=f7(b)
    c.sort()
    largest=c[-1]
    id=0
    for i in range(1,len(c)+1):
        if id==len(c):
            break
        while(id<len(c) and c[-i]+c[id]<=M):
            largest=max(largest,c[-i]+c[id])
            if largest==M:
                break
            id+=1
    print largest

Submission status: Time Limit Exceeded

Solution code:
def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]


while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    a=[0]
    for i in range(N):
        a.append(int(raw_input()))
    aa=a[:]
    #b=sorted([x+y for x in a for y in a])
    #c=[]
    #for i in range(1,len(b)):
    #    if b[i]>M:
    #        break
    #    elif b[i-1]!=b[i]:
    #        c.append(b[i-1])
    b=[x+y for x in a for y in aa]
    c=f7(b)
    c.sort()
    largest=0
    id=0
    for i in range(1,len(c)+1):
        if id==len(c) or largest==M:
            break
        while(id<len(c) and c[-i]+c[id]<=M):
            largest=max(largest,c[-i]+c[id])
            id+=1
    print largest

Submission status: Time Limit Exceeded

Solution code:
while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    a=[0]
    for i in range(N):
        a.append(int(raw_input()))
    #b=sorted([x+y for x in a for y in a])
    #c=[]
    #for i in range(1,len(b)):
    #    if b[i]>M:
    #        break
    #    elif b[i-1]!=b[i]:
    #        c.append(b[i-1])
    b=[a[x]+a[y] for x in range(N+1) for y in range(x,N+1)]
    #c=f7(b)
    c=sorted(b)
    largest=0
    id=0
    for i in range(1,len(c)+1):
        if id==len(c) or largest==M:
            break
        while(id<len(c) and c[-i]+c[id]<=M):
            largest=max(largest,c[-i]+c[id])
            id+=1
    print largest

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
while 1:
    n, lmt = map(int, raw_input().split())
    if n == 0: break
    p = [input() for i in range(n)]
    p = sorted(set(i + j for i in p for j in p))
    s = bisect(p, lmt)
    ans = 0
    for i in p[:s]:
        t = bisect(p[:s], lmt - i)
        ans = max(ans, i + p[t-1])
    print ans

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
while 1:
    n, lmt = map(int, raw_input().split())
    if n == 0: break
    p = [input() for i in range(n)] + [0]
    p = sorted(set(i + j for i in p for j in p))
    s = bisect(p, lmt)
    ans = 0
    for i in p[:s]:
        t = bisect(p[:s], lmt - i)
        ans = max(ans, i + p[t-1])
    print ans

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
while 1:
    n, lmt = map(int, raw_input().split())
    if n == 0: break
    p = [input() for i in range(n)] + [0]
    p = sorted(set(i + j for i in p for j in p))
    s = bisect(p, lmt)
    print max(i + p[bisect(p[:s], lmt - i) - 1] for i in p[:s])

Submission status: Time Limit Exceeded

Solution code:
while True:
    n, m = map(int, input().split())
    if not n:
        break

    ps = {int(input()) for _ in range(n)}
    ss = [False] * (m + 1)
    min_p, max_p = 1e8, 0
    for p in ps:
        ss[p] = True
        if min_p > p: min_p = p
        if max_p < p: max_p = p

    max_s = 0

    for t in range(1, 4):
        new_ss = [False] * (m + 1)
        for i in range(min(m, max_p * t), min_p * t - 1, -1):
            if ss[i]:
                for p in ps:
                    if i + p <= m:
                        new_ss[i + p] = True

        ss = new_ss

        p = m
        while p:
            if ss[p]:
                if max_s < p:
                    max_s = p
                break

    print(max_s)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

while True:
    n, m = map(int, input().split())
    if not n:
        break

    ps = [0] + sorted(int(input()) for _ in range(n))

    p2 = set()
    for i, pi in enumerate(ps):
        for pj in ps[i:]:
            if pi + pj > m:
                break
            p2.add(pi + pj)

    p2 = sorted(p2)

    max_s = 0
    for pi in p2:
        j = bisect_right(p2, m - pi)
        s = pi + p2[j - 1]
        if max_s < s:
            max_s = s
    print(max_s)

Submission status: Time Limit Exceeded

Solution code:
import bisect

while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    p=[0]+[int(raw_input()) for _ in xrange(n)]
    com=[0]*((n+1)**2)
    for i in xrange(n+1):
        for j in xrange(n+1):
            com[(n+1)*i+j]=p[i]+p[j]
    com.sort()
    ans=0
    for i in xrange(n+1):
        for j in xrange(n+1):
            if m-com[(n+1)*i+j]<0:continue
            index=bisect.bisect_left(com,m-com[(n+1)*i+j])
            if index==len(com):continue
            if com[index]>m-com[(n+1)*i+j]:
                if index==0:continue
                else:
                    index-=1
            ans=max(ans,com[(n+1)*i+j]+com[index])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    p=[0]+[int(raw_input()) for _ in xrange(n)]
    com=[None]*((n+1)**2)
    for i in xrange(n+1):
        for j in xrange(n+1):
            com[(n+1)*i+j]=p[i]+p[j]
    com.sort()
    ans=0
    for i in xrange(n+1):
        for j in xrange(n+1):
            tmp=m-com[(n+1)*i+j]
            if tmp<0:continue
            index=bisect.bisect_left(com,tmp)
            if index==(n+1)**2:continue
            if com[index]>tmp:
                if index==0:continue
                else:
                    index-=1
            ans=max(ans,com[(n+1)*i+j]+com[index])
        if ans==m:
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

def solve(n,m):
    p=[0]+[int(raw_input()) for _ in xrange(n)]
    com=[None]*((n+1)**2)
    for i in xrange(n+1):
        for j in xrange(n+1):
            com[(n+1)*i+j]=p[i]+p[j]
    com.sort()
    ans=0
    for i in xrange(n+1):
        for j in xrange(n+1):
            tmp=m-com[(n+1)*i+j]
            if tmp<0:continue
            index=bisect.bisect_left(com,tmp)
            if index==(n+1)**2:continue
            if com[index]>tmp:
                if index==0:continue
                else:
                    index-=1
            ans=max(ans,com[(n+1)*i+j]+com[index])
        if ans==m:
            break
    return ans

while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    print(solve(n,m))

Submission status: Time Limit Exceeded

Solution code:
def solve(darts, scores, point, target):
    if darts == 4:
        if point > target:
            return 0
        else:
            return point

    max_score = 0
    for s in scores:
        result1 = solve(darts + 1, scores, point + s, target)  # ???????????´???
        result2 = solve(darts + 1, scores, point, target)      # ?????°????????£?????´???
        max_score = max(max_score, result1, result2)
    return max_score


if __name__ == '__main__':
    # ??????????????\???
    while True:
        N, M = [int(x) for x in input().split(' ')]
        scores = [int(input()) for _ in range(N)]

        if N == 0 and M == 0:
            break

        # ???????????????????????????????¨????
        scores.sort()  # ???????????°??????????????????????????????
        ans = solve(0, scores, 0, M)

        # ???????????¨???
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
while 1:
    n,m=map(int,input().split())
    if n==0:break
    s,a=[],[0]*(n+1)
    for i in range(1,n+1):
        a[i]=int(input())
        for j in range(i+1):
            if a[i]+a[j]<=m:s+=[a[i]+a[j]]
            else:break
    s.sort()
    print(max(i+s[bisect.bisect_right(s,m-i)-1]for i in s))

Submission status: Time Limit Exceeded

Solution code:
while True:
    n,m = map(int, input().split())
    if(n|m)==0: break

    onelist = [0]
    for i in range(n):
        onelist.append(int(input()))

    twolist = set()
    for no in range(n+1):
        for no2 in range(no,n+1):
            twolist.add(onelist[no]+onelist[no2])
    twolist = sorted(twolist)

    ans = 0
    l = len(twolist)
    for no in twolist:
        for no2 in twolist:
            if no+no2 <= m:
                ans = max(ans,no+no2)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

file_input = sys.stdin

NM = file_input.readline()

import itertools

while NM != '0 0\n':
    N, M = map(int, NM.split())
    P = [int(file_input.readline()) for i in range(N)]
    P.append(0)
    P = list(set(P))
    P.sort()
    scores = map(sum, itertools.combinations_with_replacement(P, 4))
    print(max(filter(lambda x: x <= M, scores)))
    NM = file_input.readline()

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
	while True:
		n,m=map(int,input().split())
		if n==0 and m==0:
			break
		p=list()
		for i in range(n):
			p.append(int(input()))
		p.append(0)
		ls=list()
		for i in p:
			for j in p:
				if i+j<=m:
					ls.append(i+j)
		ans=0
		for x in ls:
			idx=bisect.bisect_right(ls,m-x)
			if idx==0:
				continue
			idx-=1
			ans=max(ans,x+ls[idx])

		print(ans)

if __name__=="__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
while True:
  n,m = map(int,input().split())
  if not n and not m: break
  lst = []
  lst2 = []
  for i in range(n):
    lst.append(int(input()))
  for i in lst:
    for j in lst:
      lst2.append(i + j)
  lst2 = lst2 + lst
  lst2.sort()
  ans = 0
  def search(x, l, r):
    y = len(l)
    if y == 0:
      return r
    elif y == 1:
      if x >= l[0]:
        return l[0]
      else:
        return r
    elif l[y//2] == x:
      return x
    elif l[y//2] > x:
      return search(x, l[:y//2], r)
    elif l[y//2] < x:
      r = l[y//2]
      return search(x, l[y//2 + 1:], r)
  for i in lst2:
    if i <= m:
      ans = max(ans, i + search(m - i, lst2, 0))
    else:
      break
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  while True:
    n,m = map(int,input().split())
    if not n and not m: break
    lst = []
    lst2 = []
    for i in range(n):
      lst.append(int(input()))
    for i in lst:
      for j in lst:
        lst2.append(i + j)
    lst2 = lst2 + lst
    lst2.sort()
    ans = 0
    def search(x, l, r):
      y = len(l)
      if y == 0:
        return r
      elif y == 1:
        if x >= l[0]:
          return l[0]
        else:
          return r
      elif l[y//2] == x:
        return x
      elif l[y//2] > x:
        return search(x, l[:y//2], r)
      elif l[y//2] < x:
        r = l[y//2]
        return search(x, l[y//2 + 1:], r)
    for i in lst2:
      if i <= m:
        ans = max(ans, i + search(m - i, lst2, 0))
      else:
        break
    print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
  while True:
    n,m = map(int,input().split())
    if not n and not m: break
    lst = []
    lst2 = []
    for i in range(n):
      lst.append(int(input()))
    for i in lst:
      for j in lst:
        lst2.append(i + j)
    lst2 = list(set(lst2 + lst))
    lst2.sort()
    ans = 0
    def binary(x, left, right):
      center = (left + right) // 2
      length = right - left + 1
      if length <= 0:
        return -100
      elif length == 1:
        if lst2[center] > x:
          return center - 1
        else:
          return center
      elif length == 2:
        if lst2[center] > x:
          return center - 1
        else:
          return center
      elif lst2[center] == x: return x
      elif lst2[center] < x: return binary(x, center, right)
      elif lst2[center] > x: return binary(x, left, center)
      
    for i in lst2:
      if i <= m:
        ans = max(ans, i + lst2[binary(m - i, 0, len(lst2) - 1)])
      else:
        break
    print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
  while True:
    n,m = map(int,input().split())
    if not n and not m: break
    lst = []
    lst2 = []
    for i in range(n):
      x = int(input())
      if x <= m:
        lst.append(x)
    lst2 = [i + j for i in lst for j in lst if i <= j]
    #for i in lst:
    #  for j in lst:
    #    if i + j <= m:
    #      lst2.append(i + j)
    #lst2 = list(set(lst2 + lst))
    lst2.sort()
    def binary(x, left, right):
      center = (left + right) // 2
      length = right - left + 1
      v = lst2[center]
      if length == 1 or length == 2:
        if v > x:
          return center - 1
        else:
          return center
      elif v == x: return x
      elif v < x: return binary(x, center + 1, right)
      elif v > x: return binary(x, left, center - 1)
    A = []
    #ans = 0
    for i in lst2:
      if i + lst2[-1] <= m:
        A.append(i + lst2[-1])
        #ans = max(ans, i + lst2[-1])
      elif i <= m:
        A.append(i + lst2[binary(m - i, 0 , len(lst2) - 1)])
        #ans = max(ans, i + lst2[binary(m - i, 0, len(lst2) - 1)])
      else:
        break
    print(max(A))
    #print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
  while True:
    n,m = map(int,input().split())
    if not n and not m: break
    lst = []
    lst2 = []
    lst = [int(input()) for _ in range(n)]
    lst.append(0)
    lst2 = [i + j for i in lst for j in lst if i <= j]
    #for i in lst:
    #  for j in lst:
    #    if i + j <= m:
    #      lst2.append(i + j)
    #lst2 = list(set(lst2 + lst))
    lst2.sort()
    def binary(x, left, right):
      center = (left + right) // 2
      length = right - left + 1
      v = lst2[center]
      if length == 1 or length == 2:
        if v > x:
          return center - 1
        else:
          return center
      elif v == x: return x
      elif v < x: return binary(x, center, right)
      elif v > x: return binary(x, left, center)
    A = []
    #ans = 0
    for i in lst2:
      if i + lst2[-1] <= m:
        A.append(i + lst2[-1])
        #ans = max(ans, i + lst2[-1])
      elif i <= m:
        A.append(i + lst2[binary(m - i, 0 , len(lst2) - 1)])
        #ans = max(ans, i + lst2[binary(m - i, 0, len(lst2) - 1)])
      else:
        break
    print(max(A))
    #print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
import bisect
while True:
    n, m = map(int, input().split())
    if n == 0:
        break
    p = list(int(input()) for i in range(n))
    point = [] + p
    for i in p:
        for j in p:
            a = i + j
            if a <= m and a not in point:
                point.append(a)
    point.sort()
    maxp = 0
    for i in point:
        if m - i in point:
            print(m)
            break
        pp = i + point[bisect.bisect_left(point, m - i) - 1]
        if pp > maxp:
            maxp = pp
    else:
        print(maxp)

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
    while True:
        n, m = map(int, input().split())
        if n == 0:
            break
        p = list(int(input()) for i in range(n))
        point = [] + p
        for i in p:
            for j in p:
                a = i + j
                if a <= m and a not in point:
                    point.append(a)
        point.sort()
        maxp = 0
        for i in point:
            if m - i in point:
                print(m)
                break
            pp = i + point[bisect.bisect_left(point, m - i) - 1]
            if pp > maxp:
                maxp = pp
        else:
            print(maxp)
            
if __name__=="__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May  7 22:55:31 2018

@author: maezawa
"""

def search(p, m, i):
    if i == 1:
        if m<p[0]:
            return -1
        for j, k in enumerate(p):            
            if k>m:
                return p[j-1]
            elif j==n-1:
                return p[n-1]
    else:
        dif = 2*10**8
        for j, k in enumerate(p):
            if m-k<0:
                continue
            a = search(p, m-k, i-1)
            #print(m-k, a, i-1)
            if m-k-a < dif:
                dif = m-k-a
        return m-dif

while True:
    p = []
    n, m = list(map(int, input().split()))
    if n==0 and m==0:
        break
    for i in range(n):
        p.append(int(input()))
    p.sort()
    dif = 2*10**8
    for i in range(1,5):
        a = search(p, m, i)
        if a<0:
            continue
        #print("outer",i,a)
        if m-a < dif:
            dif = m-a
    print(m-dif)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon May  7 22:55:31 2018

@author: maezawa
"""

def search(p, m, i):
    if i == 1:
        if m<p[0]:
            return -1
        for j, k in enumerate(p):            
            if k>m:
                return p[j-1]
            elif j==n-1:
                return p[n-1]
    else:
        dif = 2*10**8
        for j, k in enumerate(p):
            if m-k<0:
                break
            a = search(p, m-k, i-1)
            #print(m-k, a, i-1)
            if m-k-a < dif:
                dif = m-k-a
        return m-dif

while True:
    p = []
    n, m = list(map(int, input().split()))
    if n==0 and m==0:
        break
    for i in range(n):
        p.append(int(input()))
    p.sort()
    dif = 2*10**8
    for i in range(1,5):
        a = search(p, m, i)
        if a<0:
            continue
        #print("outer",i,a)
        if m-a < dif:
            dif = m-a
    print(m-dif)

Submission status: Time Limit Exceeded

Solution code:
def calc(s, count):
    global m, r, nums
    if s >= m or count > 4:
        return
    else:
        if r < s:
            r = s
        for n in nums:
            calc(s + n, count + 1)

while True:
    n, m = [int(n) for n in raw_input().split()]
    if n == 0 and m == 0:
        break
    else:
        r = 0
        nums = [int(raw_input()) for i in range(n)]
        calc(0, 0)
        print r

Submission status: Time Limit Exceeded

Solution code:
import bisect

while True:
    n, m = [int(n) for n in raw_input().split()]
    if n == 0 and m == 0:
        break
    else:
        r = 0
        nums = [int(raw_input()) for i in range(n)] + [0]
        temp = sorted(set([x + y for x in nums for y in nums if x + y < m]))
        for num in temp:
            index = bisect.bisect_left(temp, m - num)
            if r < num + temp[index - 1]:
                r = num + temp[index - 1]
        print r

Submission status: Time Limit Exceeded

Solution code:
import bisect

while True:
    n, m = [int(n) for n in raw_input().split()]
    if n == 0:
        break
    else:
        r = 0
        nums = [int(raw_input()) for i in range(n)] + [0]
        temp = sorted(set([x + y for x in nums for y in nums if x + y < m]))
        for num in temp:
            index = bisect.bisect_left(temp, m - num)
            if r < num + temp[index - 1]:
                r = num + temp[index - 1]
        print r

Submission status: Time Limit Exceeded

Solution code:
import bisect

while True:
    try:
        n, m = [int(n) for n in raw_input().split()]
        if n == 0:
            break
        else:
            r = 0
            nums = [int(raw_input()) for i in range(n)] + [0]
            temp = sorted(set([x + y for x in nums for y in nums if x + y < m]))
            for num in temp:
                index = bisect.bisect_left(temp, m - num)
                if r < num + temp[index - 1]:
                    r = num + temp[index - 1]
            print r
    except EOFError:
        break

Submission status: Time Limit Exceeded

Solution code:
import bisect
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    L=[input() for i in range(N)]
    L.append(0)
    S=set(i+j for i in L for j in L)
    B=sorted(S)
    maxInt=0
    for i in B:
        if i>M:break
        idx=bisect.bisect(B,M-i)
        if i+B[idx-1]<=M:
            maxInt=max(maxInt,i+B[idx-1])
    print maxInt

Submission status: Time Limit Exceeded

Solution code:
import bisect
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    L=[input() for i in range(N)]
    L.append(0)
    S=set(i+j for i in L for j in L)
    B=sorted(S)
    maxInt=0
    for i in B:
        if i>M:break
        idx=bisect.bisect(B,M-i)
        maxInt=max(maxInt,i+B[idx-1])
    print maxInt

Submission status: Time Limit Exceeded

Solution code:
import bisect
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    L=[input() for i in range(N)]
    L.append(0)
    S=set()
    for i in L:
        for j in L:
            S.add(i+j)
    B=sorted(S)
    maxInt=0
    for i in B:
        if i>M:break
        idx=bisect.bisect(B,M-i)
        maxInt=max(maxInt,i+B[idx-1])
    print maxInt

Submission status: Time Limit Exceeded

Solution code:
import bisect
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    L=[input() for i in range(N)]
    L.append(0)
    S=set(i+j for i in L for j in L)
    B=sorted(S)
    maxInt=0
    t=bisect.bisect(B,M)-1
    for i in B[:t]:
        idx=bisect.bisect(B,M-i)
        maxInt=max(maxInt,i+B[idx-1])
    print maxInt

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	N,M = map(int,raw_input().split())
	if N == 0: break
	P = set([int(raw_input()) for i in range(N)])
	ans = 0
	for i in range(2,5):
		for p in itertools.combinations_with_replacement(P,i):
			if ans < sum(p) <= M:
				ans = sum(p)
	print ans

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
while 1:
	N,M = map(int,raw_input().split())
	if N == 0: break
	P = [int(raw_input()) for i in range(N)] + [0]
	P = sorted([i+j for i in P for j in P])
	s = bisect(P,M) - 1
	print max(i + P[bisect(P,M-i) - 1] for i in P[:s])

Submission status: Memory Limit Exceeded

Solution code:
def searchclosest(plist,m):
    index=len(plist)/2
    if index==0:
        if plist[-1]<=m:
            return plist[-1]
        elif plst[0]<=m:
            return plist[0]
        else:
            return 0
    else:
        if plist[index]>m:
            return searchclosest(plist[0:index],m)
        else:
            return searchclosest(plist[index:],m)
        

while(1):
    [n,m]=[int(x) for x in raw_input().split()]
    if n==0:
        break
    else:
        p1=[]
        p2=[]
        p3=[]
        p4=[]
        P=0
        for i in range(n):
            p1.append(int(raw_input()))
        p1.sort()
        M1=searchclosest(p1,m)
        indexmaxp1=p1.index(M1)+1
        p1=p1[:indexmaxp1]
        for p in p1:
            p2=p2+[p+x for x in p1]
        p2.sort()
        M2=searchclosest(p2,m)
        indexmaxp2=p2.index(M2)+1
        p2=p2[:indexmaxp2]
        for p in p1:
            p3=p3+[p+x for x in p2]
        p3.sort()
        M3=searchclosest(p3,m)
        indexmaxp3=p3.index(M3)+1
        p3=p3[:indexmaxp3]
        for p in p1:
            p4=p4+[p+x for x in p3]
        p4.sort()
        M4=searchclosest(p4,m)
        indexmaxp4=p4.index(M4)+1
        p4=p4[:indexmaxp4]
        print max(M1,M2,M3,M4)

Submission status: Memory Limit Exceeded

Solution code:
from collections import defaultdict
while 1:
    n, lmt = map(int, raw_input().split())
    if n == 0: break
    dp = defaultdict(set)
    for _ in range(n):
        k = input()
        if k <= lmt: dp[0].add(k)
        for i in range(3):
            for j in dp[i]:
                if k + j <= lmt: dp[i+1].add(k+j)
    ans = 0
    for i in range(4):
        for j in sorted(dp[i]):
            if ans < j and lmt >= j: ans = j
            if lmt < j: break
    print ans

Submission status: Memory Limit Exceeded

Solution code:
while 1:
	N,M = map(int,raw_input().split())
	if N == 0: break
	P  = set([int(raw_input()) for i in range(N)])
	P2 = set([i+j for i in P for j in P  if i+j <= M])
	P3 = set([i+j for i in P for j in P2 if i+j <= M])
	P4 = set([i+j for i in P for j in P3 if i+j <= M])
	print max(map(max,P,P2,P3,P4))

Submission status: Accepted

Solution code:
import bisect
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    if N*M == 0:
        return False
    P = [0]+[int(input()) for _ in range(N)]
    # solve
    k = [P[i]+P[j] for i in range(N) for j in range(i, N)]
    k = sorted(k)

    ret = 0
    for tmp in k:
        if tmp > M:
            break
        else:
            r = M-tmp
            l = bisect.bisect_right(k, r)
            if l >= len(k):
                tmp += k[-1]
            elif l != 0:
                tmp += k[l-1]
            ret = max(ret, tmp)
    return ret


ans = []
while True:
    ret = solve()
    if ret:
        ans.append(ret)
    else:
        break
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import bisect
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    if N*M == 0:
        return False
    P = [0]+[int(input()) for _ in range(N)]
    # solve
    k = [P[i]+P[j] for i in range(N) for j in range(i, N)]
    k = sorted(k)

    ret = 0
    for tmp in k:
        if tmp > M:
            break
        else:
            r = M-tmp
            l = bisect.bisect_right(k, r)
            tmp += k[l-1]
            ret = max(ret, tmp)
    return ret


ans = []
while True:
    ret = solve()
    if ret:
        ans.append(ret)
    else:
        break
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
from bisect import *
while 1:
    N,M = map(int,raw_input().split())
    if N == 0: break
    P = [int(raw_input()) for i in range(N)] + [0]
    P = sorted(set(i+j for i in P for j in P))
    P = P[:bisect(P,M) - 1]
    print max(i + P[bisect(P,M-i) - 1] for i in P)