Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
INF = float('inf')

N,M = inpl()

alist = list()
for _ in range(M):
    alist.append(int(input()))

dp = [0]*(N+1)

for i in range(N+1):
    if i <= N and i not in alist:
        if i == 0 :
            dp[i] = 1
        elif i < 2:
            dp[i] += dp[i-1]
        elif i <= N:
            dp[i] += dp[i-1]
            dp[i] += dp[i-2]


print(dp[N]%1000000007)


### FIXED CODE ###

import sys,queue,copy
sys.setrecursionlimit(10**8)
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
INF = float('inf')

N,M = inpl()

alist = [False for _ in range(N+1)]
for _ in range(M):
    alist[int(input())] = True

dp = [0 for _ in range(N+1)]
dp[0] = 1
if not alist[1]:
    dp[1] = 1
for i in range(2,N+1):
    if alist[i]:
        continue
    dp[i] += dp[i-1] + dp[i-2]

print(dp[N]%1000000007)
### BUGGY CODE ###

def resolve():
	# N: 足場の個数, K: 1回で右にジャンプできる足場の数
	N, K = map(int, input().split())
	# h: 各足場の高さ
	h = list(map(int, input().split()))
	# dpテーブル宣言: dp[今いる足場の番号-1]=[最小コスト, 足場の高さ]
	dp = [[float('inf'), h_] for h_ in h]
	dp[0][0] = 0

	# k個左の足場からジャンプして来た時の最小コストを調べる
	for n in range(1, N):
		index_0 = max(0, n-K)
		h_ = dp[n][1]
		dp[n][0] = min(
			[
				abs( h_ - dp_[1] ) + dp_[0]
				for dp_ in set(map(tuple, dp[index_0:n]))
			]
		)
	print(dp[N-1][0])

resolve()

### FIXED CODE ###

def resolve():
	# N: 足場の個数, K: 1回で右にジャンプできる足場の数
	N, K = map(int, input().split())
	# h: 各足場の高さ
	# dpテーブル宣言: dp[今いる足場の番号-1]=[最小コスト, 足場の高さ]
	dp = [
		[float('inf'), int(h_)]
		for h_ in input().split()
	]
	dp[0][0] = 0
	dp[1][0] = abs(dp[0][1] - dp[1][1])

	# k個左の足場からジャンプして来た時の最小コストを調べる
	for n in range(2, N):
		index_0 = max(0, n-K)
		h_ = dp[n][1]
		dp[n][0] = min(
			[
				abs( h_ - dp_[1] ) + dp_[0]
				for dp_ in dp[index_0:n]
			]
		)
	print(dp[N-1][0])

resolve()
### BUGGY CODE ###

import copy
N=int(input())
A=[int(i) for i in input().split()]
T=sorted(set(A))
ANS=[]
for i in T:
    ans=0
    S=A.copy()
    del S[A.index(i)]
    S.sort()
    K=set(S)
    for t in K:
        c=S.count(t)
        ans+=c*(c-1)/2
    ANS.append(ans)
for k in A:
    print(int(ANS[T.index(k)]))

### FIXED CODE ###

from collections import Counter
N=int(input())
A=[int(i) for i in input().split()]
kw = Counter(A)
ans = sum([x * (x - 1) // 2 for x in kw.values()])
for i in A:
    print(ans-kw[i]+1)
### BUGGY CODE ###

import math
N = int(input())
S = input()

ans = 0

for i in range(0,1000):
    flag = False
    locknum = str(i).zfill(3)
    digit = 0
    for j in range(len(S)):
        if S[j] == locknum[digit]:
            if digit == 2:
                ans += 1
                break
            else:
                digit += 1

                    
print(ans)




                    

### FIXED CODE ###

import math,time
N = int(input())
S = input()
# length = len(S)
ans = 0
t1 = time.time()
for i in range(1000):
    locknum = str(i).zfill(3)
    a = S.find(locknum[0])
    b = S.find(locknum[1],a+1)
    c = S.find(locknum[2],b+1)
    if a!=-1 and b!=-1 and c!=-1:
        # print(i)
        ans +=1

t2 = time.time()
# print(t2-t1)                 
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

N,Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #頂点を0indexに
  G[a].append(b);G[b].append(a)
query = {}
for i in range(Q):
  p,x = map(int,input().split())
  p-=1
  if p not in query:
    query[p] = x
  else:
    query[p] += x
ans = [0 for _ in range(N)]
def dfs(v,par): #vが今いる頂点、parが親。
  if v in query:
    ans[v] += query[v]
  for u in G[v]:
    if u != par:
      ans[u] += ans[v]
      dfs(u,v)
dfs(0,-1)
print(*ans)
  
  

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

N,Q = map(int,input().split())
G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #頂点を0indexに
  G[a].append(b);G[b].append(a)
#query = {}
ans = [0 for _ in range(N)]
for i in range(Q):
  p,x = map(int,input().split())
  p-=1
  ans[p] += x

def dfs(v,par): #vが今いる頂点、parが親。
  if par != -1:
    ans[v] += ans[par]
  for u in G[v]:
    if u != par:
      dfs(u,v)
dfs(0,-1)
print(*ans)
### BUGGY CODE ###

X = int(input())
ans = [1]
if X == 1 or X == 2:
	print(1)
else:
	for i in range(2, X + 1):
		num = i
		count = 1
		while num ** i <= X:
			count += 1
			ans.append(num ** i)
	print(max(ans))

### FIXED CODE ###

x = int(input())
out = 1
for i in range(2,33):
    for j in range(2,10):
        num = i**j
        if x >= num:
            out = max(out, num)
print(out)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
here = 1
b = [1]
for x in range(k):
    here = a[here-1]
    if here not in b:
        b.append(here)
    else:
        here_is = b.index(here)
        c = k - here_is + 1
        cycle = len(b) - here_is
        group = b[here_is:]
        d = c % cycle
        if d != 0:
            here = group[d-1]
        else:
            here = group[-1]
        break




print(here)


### FIXED CODE ###

#nは街の数　kは移動の回数　k＋１個の街にいくことになる　
#最高でもn回移動すれば一つは二回訪れる街が現れる　そのあとはループする
n,k = map(int,input().split())
a = list(map(int,input().split()))

b = [-1]*(n+1) #街３に5回目の移動でついた場合、b[3]に５が入る　
tmp = [] #経路を記録していく
here = 1
count = 0 #移動回数

while True:
    if b[here] != -1: #一度訪れた街に再び来た
        roop = count - b[here] #ループの長さ　(街aに二回目に来た時の移動回数-一回目に来た時の移動回数)
        if k < count: #ループに入る前に移動が終わった時
            print(tmp[k])
        else:
            new_tmp = tmp[b[here]:]
            s = k-b[here]
            print(new_tmp[s%roop])
        break
    b[here] = count
    count += 1
    tmp.append(here)
    here = a[here-1]
### BUGGY CODE ###

from collections import Counter
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def getParents(self):
        return self.parents

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}



N, M = map(int, input().split())
friend = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    friend.union(a-1, b-1)

roots = friend.all_group_members()
ans = -1
for x in roots.values():
    ans = max(ans, len(x))
print(ans)


### FIXED CODE ###

from collections import Counter
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    def getParent(self):
        return [self.find(i) for i in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if (root_x == root_y):
            return
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x

        elif self.rank[root_y] > self.rank[root_x]:
            self.parent[root_x] = root_y

        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1

    def isSame(self, x, y):
        return self.find(x) == self.find(y)

    def memsInGroup(self, x):
        """
        O(N)かかります
        """
        root = self.find(x)
        return [i for i in range(N) if root == self.find(i)]

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))


N, M = map(int, input().split())

friend = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    friend.unite(a-1, b-1)

roots = friend.getParent()
counts = Counter(roots)

ans = max(counts.values())
print(ans)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
m = []
for i in range(n):
  m.append(min(p[:i + 1]))
for i in range(n):
  if p[i] == m[i]:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 1
pmin = p[0]
for i in range(1, n):
  if pmin >= p[i]:
    ans += 1
    pmin = p[i]
print(ans)
### BUGGY CODE ###

n,a,b = map(int,input().split())
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

sum=0
for i in range(1,n+1):
    if i==a:
        pass
    elif i==b:
        pass
    else:
        sum+=cmb(n,i)

if sum==0:
    print(0)
else:
    print(sum%(10**9+7))

### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7
def comb_mod(N,r,mod):
    r=min(n-r,r)
    X=1
    Y=1
    for i in range(r):
        X*=N-i
        Y*=i+1
        X%=mod
        Y%=mod
    return X*pow(Y,mod-2,mod)%mod

ans=(pow(2,n,mod)-1-comb_mod(n,a,mod)-comb_mod(n,b,mod)) % mod
print(int(ans))
### BUGGY CODE ###

n=int(input())
ans=n+1
i=1
while i*i<=n:
    if n%i==0 and ans > n%i+n/i:
        ans = n%i + n/i
print(ans-2)

### FIXED CODE ###

import math
n=int(input())
ans=n+1
i=1
while i<=math.sqrt(n):
    if n%i==0 and ans > i +n/i:
        ans = i + n/i
    i+=1
ans = int(ans)
print(ans-2)
### BUGGY CODE ###

import copy
from collections import deque

n = int(input())

ans = 0
array = ['7','5','3']

count = 0
d = deque()
d.append(([],set()))

while len(d) != 0:
  s,used = d.pop()
  if len(s) != 0 and int(''.join(s)) > n:
    continue
  
  if len(used) == 3:
    count += 1
    
  for c in array:
    cp_s = copy.deepcopy(s)
    cp_used = copy.deepcopy(used)
    cp_s.append(c)
    cp_used.add(c)
    d.append((cp_s,cp_used))
  
print(count)

### FIXED CODE ###

import copy
from collections import deque

n = int(input())

ans = 0
array = ['7','5','3']

count = 0
d = deque()
d.append(([],set()))

while len(d) != 0:
  s,used = d.pop()
  if len(s) != 0 and int(''.join(s)) > n:
    continue
  
  if len(used) == 3:
    count += 1  
    
  for c in array:
    cp_s = copy.deepcopy(s)
    cp_s.append(c)    
    if len(used) == 3:
      d.append((cp_s,used))
    
    else:
      cp_used = copy.deepcopy(used)
      cp_used.add(c)
      d.append((cp_s,cp_used))
  
print(count)
### BUGGY CODE ###

N, result = eval(input()), 1
List = list(map(int, input().split()))
for i in List[:N]:
    result *= i
    
print(result if result <= 10**18 else -1)

### FIXED CODE ###

n = int(input())
List = list(map(int, input().split()))
res = 1
if 0 in List:
    print(0)
    quit()
for x in List:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

DP = [[0] * N for _ in range(N)]

for i in range(N - 2, -1, -1):
  A = []
  su = 0
  for x in R[i]:
    A.append(DP[x][0] + 1)
    su += A[-1]
  for j in range(i + 1):
    DP[i][j] = su / len(A)
  if len(A) != 1:
    DP[i][i] = (su - max(A)) / (len(A) - 1)
  
  for j in range(i + 1, N):
    su = 0
    for x in R[i]:
      su += DP[x][j] + 1
    DP[i][j] = su / len(R[i])

print(min(DP[0]))

### FIXED CODE ###

N, M = list(map(int, input().split()))
st = [list(map(int, input().split())) for _ in range(M)]

R = {}
for s, t in st:
  s -= 1
  t -= 1
  if s in R:
    R[s].append(t)
  else:
    R[s] = [t]

DP = [0] * N
ans = N
D = [0] * N
for i in range(N - 2, -1, -1):
  ma = 0
  su = 0
  le = len(R[i])
  for j in R[i]:
    su += DP[j]
    ma = max(ma, DP[j])

  DP[i] = su / le + 1 
  if le == 1:
    D[i] = 0
  else:
    D[i] = DP[i] - (((su - ma) / (le - 1)) + 1)

P = [0] * N 
P[0] = 1
ma = 0
man = -1
for i in range(N - 1):
  t = P[i] / len(R[i])
  for j in R[i]:
    P[j] += t 
  t = P[i] * D[i]
  R[i].sort()
  if ma < t:
    ma = t
    man = i
 
if ma == -1:
  print(DP[0])
else:
  print(DP[0] - ma)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
M = 1000000007
a = [A[i] * A[j] for i in range(n-1) for j in range(i+1,n)]
print(sum(a)%M)

### FIXED CODE ###

import sys
input = sys.stdin.readline
M = 1000000007
n = int(input())
A = list(map(int, input().split()))
ans = 0
s = 0
for i in range(n):
    s += A[i]
    s %= M

for i in range(n):
    s = s - A[i]
    if s < 0:
        s += M
    ans += A[i] * s
    ans %= M
print(ans)
### BUGGY CODE ###

import copy


def add2(l):
    ys = []
    for i in range(len(l)):
        ys += [l[i] + x for x in l[i+1:]]
    return ys


def add(n, l):
    if not l:
        return []
    elif n == 2:
        return add2(l)
    else:
        ys = [x for x in add(n, l[1:])]
        ys += [l[0] + x for x in add(n-1, l[1:])]
        return ys


def main():
    n, a = (int(x) for x in input().split())
    xs = [int(x) for x in input().split()]

    ys = copy.deepcopy(xs)
    count = len(list(filter(lambda x: x == a, ys)))
    for i in range(2, n+1):
        ys = add(i, xs)
        count += len(list(filter(lambda x: x == a * i, ys)))

    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
n,avea=tuple(map(lambda x:int(x),input().split()))
x=list(map(lambda x:int(x), input().split()))
x=np.array(x)
x=x-avea
w=max(abs(min(x)),abs(max(x)))*n
dp=np.zeros((n+1,2*w+1),dtype=int)
dp[0,w]=1
for i in range(n):
    for j in range(2*w+1):
        if 0<=j-x[i]<=2*w:
            dp[i+1,j]=dp[i,j]+dp[i,j-x[i]]
        else:
            dp[i+1,j]=dp[i,j]
print(dp[n,w]-1)
### BUGGY CODE ###

import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
dprint("n, k = ", n, k)

lx = 0
rx = max(A)
ans = 0
while (int(lx) < int(rx)):
    x = (rx + lx) / 2
    dprint("lx, x, rx = ", lx, x, rx)
    n = 0
    for i in range(len(A)):
        n += math.ceil(A[i] / x) - 1
        if n > k: break
    dprint("n = ", n)
    if n <= k:
        dprint(" smaller x")
        rx = x
    else:
        dprint(" cut less, bigger x")
        lx = x

ans = math.ceil(rx)
print(ans)


### FIXED CODE ###

import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
dprint("n, k = ", n, k)

lx = int(0)   # NG
rx = int(1e9) # OK
#ans = 0
while ((rx-lx)>1):
    x = (rx + lx) // 2
    dprint("lx, x, rx = ", lx, x, rx)
    n = 0
    for i in range(len(A)):
        #n += math.ceil(A[i] / x) - 1
        n += (A[i]-1) // x
        if n > k: break
    dprint("n = ", n)
    if n <= k:
        dprint(" smaller x")
        rx = x
    else:
        dprint(" cut less, bigger x")
        lx = x

#ans = math.ceil(rx)
print(rx)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
total = 0
for i in range(n - 1):
    for j in range(i+1, n):
        total += (a[i] * a[j])
ans = total % (10 ** 9 + 7)
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a_sum = sum(a)
a_list = []
for num in a:
    a_sum -= num
    a_list.append(a_sum)
total = 0
for i in range(n-1):
    ans = a[i] * a_list[i]
    total += ans
    if total > 10 ** 9 + 7:
        total = total % (10 ** 9 + 7)
print(total)
### BUGGY CODE ###

s,n=input(),int(input())
ss=[s[i:i+j+1] for i in range(len(s)) for j in range(5)]
print(sorted(set(ss), key=sorted(ss).index)[n-1])

### FIXED CODE ###

s=input()
n=int(input())
ss=[]
for i in range(len(s)):
  for j in range(5):
    ss.append(s[i:i+j+1])
ss.sort()

kk=1
for i in range(len(ss)):
  if kk==n:
    print(ss[i])
    break
  if ss[i]!=ss[i+1]:
    kk+=1
### BUGGY CODE ###

N, W = map(int, input().split())
 
dp = [-1] * (W + 1)
dp[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        if dp[i] == -1:
            continue
        if dp[i + w] < dp[i] + v:
            dp[i + w] = dp[i] + v
print(max(dp))

### FIXED CODE ###

# DP
def main():
    N, W = map(int, input().split())
 
    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))
 
 
main()
### BUGGY CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))

# tmp1 = A[-1] - A[0]
# tmp2 = A[-1] - (20 - A[0] - A[-1])
# tmp2 = A[-1] - A[1]

# print(min(tmp1, tmp2))
# # print(A[-1]-A[0])

ans = []
for i in range(N):
    tmp = 0
    I = A[i]
    for j in range(N-1):
        index = i + j + 1
        if index >= N:
            index -= N
        J = A[index]
        if I < J:
            tmp += J - I
        else:
            tmp += K - I + J
        # print(I,J, tmp)
        I = J
    ans.append(tmp)

# print(ans)
print(min(ans))

### FIXED CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))

# tmp1 = A[-1] - A[0]
# tmp2 = A[-1] - (20 - A[0] - A[-1])
# tmp2 = A[-1] - A[1]

# print(min(tmp1, tmp2))
# # print(A[-1]-A[0])

# ans = []
ans = -1
for i in range(N):
    # 右方向
    tmp = A[-1] - A[i]
    if i != 0:
        tmp += K - A[-1] + A[i-1]
    
    if ans == -1:
        ans = tmp
    elif ans > tmp:
        ans = tmp
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]

pre = [[] for _ in range(n)]

for city in p:
    pre[city[0]-1].append(city[1])

for city in p:
    pref = "{:0>6}".format(city[0])

    years = pre[city[0] - 1]
    years.sort()
    y = years.index(city[1]) + 1

    year = "{:0>6}".format(y)
    print(pref + year)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
p = [list(map(int, input().split()+[i])) for i in range(m)]

p.sort()
cnt = 0
pre = -1

for city in p:
    if city[0] == pre:
        cnt = cnt + 1
    else:
        pre = city[0]
        cnt = 1

    city.append("{:0>6}{:0>6}".format(city[0], cnt))

p.sort(key = lambda x: x[2])

for city in p:
    print(city[3])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
mod = 10**9+7

def comb(n, r):
    if 2*r > n: comb(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % mod

def dfs(v, Pa=-1):
    for u in to[v]:
        if u == Pa: continue
        dfs(u, v)
        size[v] += size[u]
        dp[v] *= dp[u] % mod
        dp[v] *= comb(size[v], size[u]) % mod
    size[v] += 1

def bfs(v, Pa=-1, P_val=1, P_sz=0):
    ans[v] = P_val * dp[v] * comb(n-1, P_sz) % mod
    for u in to[v]:
        if u == Pa: continue
        val = ans[v] * INV(dp[u]*comb(n-1, size[u])) % mod
        bfs(u, v, val, n-size[u])

n = int(input())
to = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x : int(x)-1, input().split())
    to[a].append(b)
    to[b].append(a)

fac = [1] * (n+2)
inv = [1] * (n+2)

for i in range(2, n+1):
    fac[i] = fac[i-1] * i % mod
INV = lambda x: pow(x, mod-2, mod)
inv[n] = INV(fac[n])
for i in range(n-1, 1, -1):
    inv[i] = inv[i+1] * (i+1) % mod

dp = [1] * n
size = [0] * n
ans = [0] * n

dfs(0)
bfs(0)
print(*ans, sep='\n')

### FIXED CODE ###

import sys

def solve():
    input = lambda: sys.stdin.readline().rstrip()
    sys.setrecursionlimit(10 ** 7)
    mod = 10 ** 9 + 7

    def comb(n, r):
        if r > n: return 0
        return fac[n] * inv[r] * inv[n - r] % mod

    def dfs(v, Pa=-1):
        for u in to[v]:
            if u == Pa: continue
            dfs(u, v)
            size[v] += size[u]
            dp[v] *= dp[u] % mod
            dp[v] *= inv[size[u]] % mod
        dp[v] *= fac[size[v]] % mod
        size[v] += 1

    def bfs(v, Pa=-1, P_val=1, P_sz=0):
        ans[v] = P_val * dp[v] * comb(n - 1, P_sz) % mod
        for u in to[v]:
            if u == Pa: continue
            val = ans[v] * INV(dp[u] * comb(n - 1, size[u])) % mod
            bfs(u, v, val, n - size[u])

    n = int(input())
    to = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        to[a].append(b)
        to[b].append(a)

    fac = [1] * (n + 2)
    inv = [1] * (n + 2)

    for i in range(2, n + 1):
        fac[i] = fac[i - 1] * i % mod
    INV = lambda x: pow(x, mod - 2, mod)
    inv[n] = INV(fac[n])
    for i in range(n - 1, 1, -1):
        inv[i] = inv[i + 1] * (i + 1) % mod

    dp = [1] * n
    size = [0] * n
    ans = [0] * n

    dfs(0)
    bfs(0)
    print(*ans, sep='\n')

if __name__ == '__main__':
    solve()
### BUGGY 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()



### FIXED CODE ###

import bisect
def main():
	while True:
		n,m=map(int,input().split())
		if n==0 and m==0:
			break
		p=[0]+sorted([int(input()) for i in range(n)])
		s=list()
		for i in range(n+1):
			for j in p[i:]:
				if p[i]+j>m:
					break
				s+=[p[i]+j]
		s.sort()
		print(max(i+s[bisect.bisect_right(s,m-i)-1] for i in s))

if __name__=="__main__":
	main()