'''
双向dfs, 先枚举前一半的所有可能出现的额组合，并进行存表，
然后枚举后面一半所有可能的组合的和，枚举过程中在前面一半
的数值表中二分查找最优配对的值

'''


import bisect

W, N = map(int, input().split())
arr = []
for i in range(N):
    arr.append(int(input()))

arr.sort(reverse=True)


visit = set()
def dfs(idx, cur_sum, max_idx):
    if cur_sum not in visit:
        visit.add(cur_sum)

    if idx >= max_idx:
        return

    if cur_sum + arr[idx] <= W:
        dfs(idx+1, cur_sum+arr[idx], max_idx)
    dfs(idx+1, cur_sum, max_idx)

dfs(0, 0, len(arr)//2)
val_set = list(visit)
val_set.sort()

ans = [0]
def solve(idx, cur_sum, max_idx):
    target = W-cur_sum
    #search_idx = val_set.bisect_right(target)
    search_idx = bisect.bisect_right(val_set, target)
    if search_idx-1 >= 0 and search_idx-1 < len(val_set):
        ans[0] = max(ans[0], cur_sum + val_set[search_idx-1])

    if idx >= max_idx:
        return

    if cur_sum + arr[idx] <= W:
        solve(idx+1, cur_sum+arr[idx], max_idx)
    solve(idx+1, cur_sum, max_idx)


solve(len(arr)//2, 0, len(arr))
print(ans[0])