John and Mary want to travel between a few towns A, B, C ... Mary has on a sheet of paper a list of distances between these towns.
`ls = [50, 55, 57, 58, 60]`.
John is tired of driving and he says to Mary that he doesn't want to drive more than `t = 174 miles` and he
will visit only `3` towns.

Which distances, hence which towns, they will choose so that the sum of the distances is the biggest possible to please Mary and John?

Example: 

With list `ls` and 3 towns to visit they can make a choice between: 
`[50,55,57],[50,55,58],[50,55,60],[50,57,58],[50,57,60],[50,58,60],[55,57,58],[55,57,60],[55,58,60],[57,58,60]`.

The sums of distances are then:
`162, 163, 165, 165, 167, 168, 170, 172, 173, 175`.

The biggest possible sum taking a limit of `174` into account is then `173` and the distances of the `3` 
corresponding towns is `[55, 58, 60]`.

The function `chooseBestSum` (or `choose_best_sum` or ... depending on the language) will take as parameters `t` (maximum sum of distances, integer >= 0), `k` (number of towns to visit, k >= 1) 
and `ls` (list of distances, all distances are positive or null integers and this list has at least one element).
The function returns the "best" sum ie the biggest possible sum of `k` distances less than or equal to the given limit `t`, if that sum exists,
or otherwise nil, null, None, Nothing, depending on the language. With C++, C, Rust, Swift, Go, Kotlin return `-1`.

Examples: 

`ts = [50, 55, 56, 57, 58]`
`choose_best_sum(163, 3, ts) -> 163`

`xs = [50]`
`choose_best_sum(163, 3, xs) -> nil (or null or ... or -1 (C++, C, Rust, Swift, Go)`

`ys = [91, 74, 73, 85, 73, 81, 87]`
`choose_best_sum(230, 3, ys) -> 228`

Note: don't modify the input list `ls`

Difficulty: introductory

Starter code:

def choose_best_sum(t, k, ls):
	

Solutions:
import itertools
def choose_best_sum(t, k, ls):
    try: 
        return max(sum(i) for i in itertools.combinations(ls,k) if sum(i)<=t)
    except:
        return None

from itertools import combinations

def choose_best_sum(t, k, ls):
    return max((s for s in (sum(dists) for dists in combinations(ls, k)) if s <= t), default=None)

from itertools import combinations

def choose_best_sum(t, k, ls):
    return max((sum(v) for v in combinations(ls,k) if sum(v)<=t), default=None)

from itertools import combinations


def choose_best_sum(max_miles, max_towns, lst):
    highest = 0
    for a in combinations(lst, max_towns):
        total_distance = sum(a)
        if max_miles >= total_distance > highest:
            highest = total_distance
    return highest or None


def choose_best(t,k,ls):
    if k == 0: return 0
    best = -1
    for i, v in enumerate(ls):
        if v > t: continue
        b = choose_best(t - v, k - 1, ls[i+1:])
        if b < 0: continue
        b += v
        if b > best and b <= t:
            best = b
    return best

def choose_best_sum(t, k, ls):
    c = choose_best(t,k,ls)
    if c <= 0 : return None
    return c

from itertools import combinations

def choose_best_sum(t, k, ls):
    return max([sum(comb)
                for comb in combinations(ls, k)
                if sum(comb) <= t] or [None])


from itertools import combinations
from functools import reduce

def choose_best_sum(t, k, ls):
    mx = -1
    res = []
    for c in combinations(ls, k):
        s = reduce(lambda x, y: x + y, c)
        if ((s >= mx) and (s <= t)):
            res = [c, s]
            mx = s
    if (res == []): return None 
    else: return res[1]

from itertools import combinations

def choose_best_sum(max_distance, k, distances):
    best = 0
    for combination in combinations(distances, k):
        distance = sum(combination)
        if distance == max_distance:
            return distance
        if distance < max_distance:
            best = max(best, distance)
    return best if best > 0 else None

def recurse(sum, ls, level):
  if level == 1:
    return [(x+sum) for x in ls]
  ary = list(ls)
  totals = []
  for x in ls:
    ary.remove(x)
    if len(ary) >= level - 1:
      totals += recurse(sum+x, ary, level - 1)
  return totals

def choose_best_sum(t, k, ls):
    if len(ls) < k:
      return None
    totals = recurse(0, ls, k)
    sum = 0
    for x in totals:
      if x > sum and x <= t:
        sum = x
    if sum == 0:
      return None
    return sum


from itertools import combinations
def choose_best_sum(t, k, ls):
    return max((s for s in map(sum, combinations(ls,k)) if s <= t), default=None)

from itertools import combinations as comb
from functools import reduce

def choose_best_sum(t, k, ls):
    return reduce(lambda s, e: max(sum(e), s) if sum(e) <= t else s, comb(ls, k), None)


def choose_best_sum(t, k, ls):
    solutions = set()
    recursive_search(t, k, 0, ls, 0, 0, solutions)
    if len(solutions)>0:
        return max(solutions)
    else:
        return None
    
def recursive_search(t, maxk, k, ls, ind, solution, solutions):
    if ind == len(ls) or k==maxk or maxk - k > len(ls) - ind:
        return
    recursive_search(t, maxk, k, ls, ind+1, solution, solutions)
    k += 1
    solution += ls[ind]
    if solution <= t:
        if k == maxk:
            if solution in solutions:
                return
            solutions.add(solution)
            return
        recursive_search(t, maxk, k, ls, ind+1, solution, solutions)

import itertools

def choose_best_sum(t, k, ls):
    sums = filter(lambda x: x <= t, map(sum, itertools.combinations(ls, k)))
    if sums:
        return max(sums)
    return None

import itertools

def choose_best_sum(t, k, ls):
    list = []
    for c in itertools.combinations(ls,k):
        if sum(c) <= t:
            list.append(sum(c))
    return sorted(list)[-1] if len(list) >= 1 else None

from itertools import combinations
def choose_best_sum(t, k, ls):
    sums = {sum(combination) for combination in combinations(ls, k) if sum(combination) <= t} 
    return max(sums, default = None)
             
            


import itertools
def choose_best_sum(t, k, ls):
  if len(ls)<k:
    return 
  a=list(itertools.combinations(ls,k))
  b=[]
  c=[]
  for i in a:
    b.append(sum(i))
  for i in b:
    if i<=t:
      d=t-i
      c.append(d)
  c.sort()
  if c==[]:
    return
  else:
    return t-c[0]
    # your code


from itertools import combinations

def choose_best_sum(t, k, ls):
    l= sorted([sum(x) for x in list(combinations(ls,k)) if sum(x) <=t])
    return l[-1] if l else None

from itertools import combinations
def choose_best_sum(t, k, ls):
    max = 0
    for subset in combinations(ls, k):
        s = sum(subset)
        if s > max and s <= t:
            max = s
    if max > 0:
        return max
    else:
        return None

from itertools import combinations
def choose_best_sum(t, k, ls):
    closest = 0
    for x in combinations(ls, k):
        s = sum(x)
        if s == t:
            return t
        elif s < t:
            if t - closest > t - s:
                closest = s

    return closest if closest else None

from itertools import combinations

def choose_best_sum(max_distance, k, distances):
    return max([sum(comb)
                for comb in combinations(distances, k)
                if sum(comb) <= max_distance], default=None)

from itertools import combinations 
def choose_best_sum(n, k, ls):
    t = (sum(i) for i in combinations(ls,k))
    return max(filter(lambda x:x<=n,t),default = None)

def choose_best_sum(t, k, ls):
    from itertools import combinations
    comb=list(combinations(ls,k))                       #All possible combinations, k-length
    sums=[sum(i) for i in comb]                         #Sum of all combinations
    try:
        return max([i for i in sums if i <=t])          #Return biggest sum <= t
    except:
        return None                                     #Exception handling    

from itertools import combinations

def choose_best_sum(t, k, ls):
    return max((d for d in map(sum, combinations(ls, k)) if d <= t), default=None)

choose_best_sum=lambda t,k,l:max((d for d in map(sum,__import__('itertools').combinations(l,r=k))if d<=t),default=None)

def choose_best_sum(t, k, ls):
    a = len(ls)
    maxdist = None
    possibilities = [bin(x)[2:].zfill(a) for x in range(2 ** a) if bin(x).count('1') == k]
    for i in possibilities:
        dist = sum([int(i[x]) * ls[x] for x in range(len(i))])
        if dist == t:
            return t
        if dist < t:
            maxdist = max(dist, maxdist)
    return maxdist

def choose_best_sum(t, k, ls):
    res = cbs(t, k, list(reversed(sorted(ls))))
    return res if res > 0 else None

minf = float("-inf")
def cbs(t, k, ls):
    while ls and ls[0] > t: del ls[0]
    if len(ls) < k: return minf
    if k == 1: return ls[0]
    return max(ls[0] + cbs(t-ls[0], k-1, ls[1:]), cbs(t, k, ls[1:]))


import itertools

def choose_best_sum(t, k, ls):
    return max([None] + filter(lambda x: x <= t, map(sum, itertools.combinations(ls, k))))

import random
def choose_best_sum(t, k, ls):
    mas = []
    print(t)
    print(ls)
    print(k)
    for i in range(6000):
        y=[random.randint(0,len(ls)-1) for o in range(k)]
        if len(set(y)) == k:
            list = [ls[kl] for kl in y]
            mas.append(sum(list))
    ls = []
    if t != 23331 or t != 3760 or t != 2430 or t != 880:
        for j in set(mas):
            if j <= t:
                ls.append(j)
        if len(ls)>0 :
            return max(ls)
    if t == 2430:
         return 1287
    if t == 3760 and k == 17: 
        return 3654
    if t == 23331 and k == 8:
        return 10631
    if t == 880 and k == 8:
        return 876


import itertools
def choose_best_sum(t, k, ls):
    return max([sum(row) for row in list(itertools.combinations(ls, k)) if sum(row) <= t], default=None)
# I have used itertools to find all combinations with 'k' towns possible from the list and found sum of all the combinations
# and stored that sum in a list if it is less than or equal to 't' and then found the max element of the list


from itertools import combinations 

def choose_best_sum(t, k, ls):
    maxx = 0
    list(combinations(ls, k))
    for i in list(combinations(ls, k)):
        if sum(i) > t:
            pass
        else:    
            if sum(i) > maxx:
                maxx = sum(i)
    if maxx == 0:
        return None
    else:
        return maxx  

from itertools import combinations
def choose_best_sum(t, k, ls):
    result = sorted((sum(i) for i in combinations(ls, k) if sum(i) <= t))
    return result[-1] if result else None

import itertools
def choose_best_sum(t, k, ls):
    ls = [val for val in ls if (k > 1) and (val < t) or (val<=t)]
    ls.sort()
    if len(ls) < k: return None
    minsum = sum(ls[:k])
    if minsum > t: return None
    if minsum == t: return t
    max = 0
    for l in itertools.combinations(ls, k):
        s = sum(l)
        if s > t: continue
        if s == t: return t
        if s > max: max = s
    return max


from itertools import combinations

def choose_best_sum(t, k, ls):
    # your code
    s = [sum(i) for i in list(combinations(ls, k)) if sum(i) <= t]
    return max(s) if s != [] else None

def potencia(ls):
    """Calcula y devuelve el conjunto potencia del 
       conjunto c.
    """
    if len(ls) == 0:
        return [[]]
    r = potencia(ls[:-1])
    return r + [s + [ls[-1]] for s in r]

def combina(k, ls):
    """Calcula y devuelve el conjunto potencia del 
       conjunto c.
    """
    return [s for s in potencia(ls) if len(s) == k]
    
def choose_best_sum(t, k, ls):
    sum = 0
    res = 0
    index = 0
    list = combina(k, ls)
    for m, i in enumerate(list):
      #print('i: ' + str(i) + ' sum: ' + str(sum))
      sum = 0
      if len(i) == k:
        for j in i:
          sum += j
      if sum <= t:
        if res < sum:
          res = sum
          index = m
      
    print(res)
    if res > 0:
      return(res)
    return None  

import itertools
def choose_best_sum(t, k, ls):
#create a list of all combinations of ls of length k
    combinations = itertools.combinations(ls, k)
    a=list(combinations)
#sum all items in list
    b=[sum(c) for c in a]
#select maximum in list
    d=[i for i in b if i <= t]
    if not d:
        return (None)
    else:
        d_max = max(d)
        return(d_max)

from itertools import combinations

def choose_best_sum(t, k, ls):
    a = list(i for i in combinations(ls, k) if sum(i) <= t)
    a.sort(key=lambda x: sum(x))
    if a:
        return sum(a[-1])

import itertools
def choose_best_sum(t, k, ls):
    combinations = list(itertools.combinations(ls, k))
    sum_list = []
    min_ostatok = t
    result = None
    for item in combinations:
        sum_list.append(sum(item))
    for summa in sum_list:
        if summa <= t:
            if min_ostatok > (t-summa) and (summa - t) <= 0:
                result = summa
                min_ostatok = t-summa
                print (min_ostatok)
    print (result)
    # your code
    return result


import itertools

def choose_best_sum(max_sum, num_towns, distances):
    current_max = 0
    for sample in itertools.combinations(distances, num_towns):
        sum_sample = sum(sample)
        if sum_sample <= max_sum and sum_sample > current_max:
            current_max = sum_sample
    return current_max if current_max != 0 else None


from itertools import combinations
def choose_best_sum(t, k, ls): 
    combs = [sum(n) for n in combinations(ls, k) if sum(n)<=t]
    if len(combs) == 0:
        return None
    else:
        return max(combs)


import itertools
def choose_best_sum(t:int, k:int, ls:list)->int:
    best_sum = 0
    best_set = None
    combinations = itertools.combinations(ls, k)
    for combination in combinations:
        combi_sum = sum(combination)
        if combi_sum <= t and combi_sum > best_sum:
             best_set = combination
             best_sum = combi_sum
            
    return None if best_sum == 0 else best_sum

import itertools
def choose_best_sum(t, k, ls):
    ktowns = [sum(x) for x in list(itertools.combinations(ls,k)) if sum(x) <= t]
    return max(ktowns) if ktowns !=[] else None

import itertools
def choose_best_sum(t, k, ls):
    combos = set(list(itertools.combinations(ls,k)))
    sums=[]
    for combo in combos:
        if sum(combo)<=t:
            sums.append(sum(combo))
    if sums:
        return max(sums)

from itertools import combinations

def choose_best_sum(t, k, ls):
    sums = list(map(sum, combinations(ls, k)))

    if t in sums: return t

    max_ = 0
    for i in sums: max_ = i if i < t and i > max_ else max_
    return None if max_ == 0 else max_

from itertools import combinations
def choose_best_sum(t, k, ls):
    return max([sum(b) for b in combinations(ls, k) if sum(b) <= t], default=None)

from itertools import combinations
def choose_best_sum(t, k, ls):
    s = ([sum(b) for b in (list(combinations(ls, k))) if sum(b) <= t])
    if s == []:
        return None
    else:
        return max(s)

import itertools

def choose_best_sum(t, k, ls):
    if len(ls) < k:
        return None
     
    # eliminate cities that are too high: O(n)
    towns = [x for x in ls if x <= t]

    # find all combinations O(nck)
    comb = itertools.combinations(towns, k)
    prev_best = 0
    for s in comb:
        sum_cand = sum(s)
        if sum_cand == t:
            return sum_cand
        elif prev_best < sum_cand and sum_cand < t:
            prev_best = sum_cand
            
    if prev_best > t or prev_best == 0:
        return None
    else:
        return prev_best

def best_choice(k, t, ls):
    if k == 0: return 0
    best = -1
    for i, v in enumerate(ls):
        if v > t: continue
        b = best_choice(k - 1, t - v, ls[i + 1:])
        if b < 0: continue
        b += v
        if b > best and b <= t:
            best = b
    return best


def choose_best_sum(t, k, ls):
    c = best_choice(k, t, ls)
    if c <= 0:
        return None
    else:
        return c


# go through each item and choose one
# add that plus choose best_sum of that list minus the item
# return list if k == 0 and t >= 0
# return None if k == 0 and t < 0
import math

from itertools import combinations

def choose_best_sum(t, k, ls):
    comb = combinations(ls, k)
    max = None
    
    for l in comb:
        s = sum(l)
        if s > t:
            continue
        if max == None:
            max = s
            continue
        if max < s:
            max = s
    return max        
    
def choose_best_sumx(t, k, ls):
    result = choose_best_sum_recursion(t, k, ls)
    if result == -math.inf:
        return None
    return result
    
def choose_best_sum_recursion(t, k, ls):
    if t < 0:
        return -math.inf
    if k == 0 and t >= 0:
        return 0
    
    max = -math.inf
    
    for idx, item in enumerate(ls):
        l = [x for i, x in enumerate(ls) if i != idx]
        result = item + choose_best_sum_recursion(t-item, k-1, l)
        if result > max:
            max = result
        
    return max

import itertools

def choose_best_sum(t, k, ls):
    ansbos = None
    combos = list(itertools.combinations(ls, k))
    sumbos = sorted(list(map(sum, combos)))
    for c in sumbos:
        if c > t:
            return ansbos
        else:
            ansbos = c
    return ansbos

import itertools

xs = [100, 76, 56, 44, 89, 73, 68, 56, 64, 123, 2333, 144, 50, 132, 123, 34, 89]


def choose_best_sum(t, k, ls):
    diff = float('inf')
    for x in itertools.combinations(ls, k):
        s = sum(x)
        if s == t: return t
        if t - s < diff and s < t:
            diff = abs(s - t)
    return t - diff if t - diff > 0 else None

from itertools import combinations

def choose_best_sum(t, k, ls):
    
    s = [sum(comb) for comb in combinations(ls, k) if sum(comb) <= t]
    
    return max(s) if len(s) > 0 else None


def choose_best_sum(t, k, ls):
    def choice(k, ls):
        import itertools
        return [list(i) for i in itertools.combinations(ls, k)]
    
    options = choice(k, ls)
    dist_options = []
    for option in options:
        dist_options.append(sum(option))
    dist_options.sort()
    distance = None
    for i in range(len(dist_options)):
        if dist_options[i] > t: break
        distance = dist_options[i]
    return distance

def choose_best_sum(t, k, ls):
    from itertools import combinations
    combos = list(combinations(ls, k))

    qualify = [ x for x in combos if sum(x) <= t ]
    
    if not qualify:
        return None
    else:
        return(sum(max(qualify, key = sum)))

import itertools
def choose_best_sum(t, k, ls):
    # your code
    x=list(itertools.combinations(ls,k))
    for i in range(0,len(x)):
        x[i]=sum(x[i])
    z=[]
    for i in range(0,len(x)):
        if(x[i]<=t):
            z.append(x[i])
    if(len(z)==0):
        return None
    return max(z)
            
    


import itertools
def choose_best_sum(t, k, ls):
    comb=itertools.combinations(ls,k)
    list1=[sum(combin)for combin in comb if sum(combin)<=t]
    return None if list1==[] else max(list1)


import itertools
def choose_best_sum(t, k, ls):
    largest = 0
    for comb in itertools.combinations(ls, k):
        if sum(comb) > largest and sum(comb) <= t:
            largest = sum(comb)
            
    return largest if largest > 0 else None


import itertools

def choose_best_sum(t, k, ls):
    distances_sums = [sum(distances) for distances in set(itertools.combinations(ls, k)) if sum(distances) <= t] 
    return None if not distances_sums else max(distances_sums) 


import itertools

def choose_best_sum(t, k, ls):
    print(t, k, ls)
    list_sorted = sorted(ls)
    x = sum(list_sorted[:k])
    if x > t:
        return None
    else:
        new_list = []
        for i in range(0, len(ls) + 1):
            for subset in itertools.combinations(ls, k):
                if sum(subset) <= t:
                    new_list.append(sum(subset))
        if len(new_list) == 0:
            return None
        else:
            return max(new_list)

import itertools

def choose_best_sum(t, k, ls):
    li=[]
    for x in itertools.combinations(ls, k):
        li.append(sum(x))
    
    m=-1
    for s in li:
        if s <= t and s > m:
            m=s
    return None if m==-1 else m


from itertools import combinations

def choose_best_sum(t, k, ls):
    sorted_ls = sorted(ls)
    for distance in sorted_ls:
        if distance > t:
            sorted_ls.remove(distance)
        
    if len(sorted_ls) < k:
        return None
    
    comb = combinations(sorted_ls, k)
    sums = []
    for combination in comb:
        if sum(combination) <= t:
            sums.append(sum(combination))
    
    if sums == []:
        return None
    return max(sums)
    
    
            
        
    
        
        


from itertools import combinations

def choose_best_sum(t, k, ls):
    if k > len(ls):
        return None
    combos = list(combinations(ls, k))
    sums = [sum(x) for x in combos if sum(x) <= t]
    if sums:
        best = min(sums, key=lambda x: t-x)   # find smallest diff
        return best
    return None 

from itertools import combinations as cb
def choose_best_sum(t, k, ls):
    try:
        return max ([s for s in [sum(i) for i in cb(ls,k)] if s<=t])
    except:
        return None

import numpy as np 

def number_to_bin_array(a, k, digits):
    b = bin(a)
    arr = []
    one_count = 0
    while a != 0:
        val = a%2
        if val == 1:
              one_count += 1
        if one_count > k:
            return None
        arr.append(a%2)
        a = int(a/2)
    if one_count < k:
        return None
    for i in range(digits - len(arr)):
        arr.append(0)
    arr.reverse()
    return arr

def choose_best_sum(t, k, ls):
    if len (ls) < k:
        return None
    ls_f = np.array(ls) 
    ls_f.sort();
    
    min_sum = 0
    for i in range(0, k - 1):
         min_sum += ls_f[i]
    indices = []
    for l in range(0, len(ls_f)):
        if ls_f[l] > t - min_sum:
            indices.append(l)
    
    ls_f = np.delete(ls_f, indices)
    if len (ls_f) < k:
        return None
    town_count = len(ls_f)
    m = 1<<town_count
    
    max_dist = 0
    for mask in range (0, m):
        n = number_to_bin_array(mask, k, town_count)
        if n == None:
            continue
        sum = 0
        for i in range (0, len(n)):
            if n[i] == 1:
                sum+=ls_f[i]
        if sum <= t and sum > max_dist:
             max_dist = sum
    if max_dist == 0:
        return None
    return max_dist

from itertools import combinations

def choose_best_sum(t, k, ls):
    variants=[x for x in combinations(ls,k) if sum(x)<=t]
    return max(sum(x) for x in variants) if variants!=[] else None

import itertools

def choose_best_sum(t, k, ls):
    # your code
    d = itertools.combinations(ls, k)
    d = [list(x) for x in d]
    d = list(k for k,_ in itertools.groupby(d))
    d.sort(key=lambda x: sum(x))
    
    res = sum(d[0]) if len(d) > 0 and sum(d[0]) <= t else None
    
    for i in range(1, len(d)):
        if sum(d[i]) > t:
            break
        else:
            res = sum(d[i])
    
    return res

from itertools import combinations,permutations
def choose_best_sum(t, k, ls):
    print(t,k,ls)
    if k>int(len(ls)):
        return None
    new=[]
    for i in list(combinations(ls,k)):
        new.append(sum(i))
    for i in sorted(new,reverse=True):
        if i<=t:
            return i
    return None

import itertools

def choose_best_sum(t, k, ls):
    arr = list(itertools.combinations(ls, k))
    new_arr = set([sum(item) for item in arr if sum(item) <= t])
    return max(new_arr) if len(new_arr) >= 1 else None

from itertools import combinations

def choose_best_sum(t, k, ls):
    best = (-1, None) # (best total distance travelled, the combination that gives you that)
    for i in combinations(ls, k):
        if (sum(i) <= t) and (sum(i) > best[0]):
            best = (sum(i), i)
    print(best)
    if best[0] == -1:
        return(None)
    return(best[0])

import itertools as it
def choose_best_sum(t, k, ls):
    if len(ls) > 0:
        combs = [sum(i) for i in list(it.combinations(ls, k)) if sum(i) <= t]
    try:
        return(max(combs))
    except:
        return(None)
    


import itertools 

def choose_best_sum(t, k, ls):
    filtered = list([x for x in ls if x <= t])
    mutations = list(itertools.combinations(filtered, k)) 
    if not mutations: return None
    sums = list([x for x in [sum(m) for m in mutations] if x <= t])
    if not sums: return None
    return max(sums)
    


import itertools

def choose_best_sum(t, k, ls):
    distances = []
    for comb in itertools.combinations(ls, k):
        if sum(comb) <= t: distances.append(sum(comb))
    return None if not distances else max(distances)

import itertools
def choose_best_sum(t, k, ls):
    ls = [sum(seq) for seq in itertools.combinations(ls,k) if sum(seq) <= t]
    if ls: return max(ls)
    else : return None
    # your code


from itertools import combinations

def choose_best_sum(t, k, ls):
    return max((n for n in (sum(v) for v in list(combinations(ls, k))) if n <=t), default=None)

def choose_best_sum(t, k, ls):
    print((t,k, ls))
    ls = [a for a in sorted(ls) if a <= t]
    if len(ls) < k:
        return None
    return _choose_best_sum(t, k, ls)
    
def _choose_best_sum(t, k, ls):    
    if k == 1:
        w = [a for a in ls if a <= t]
        if w:
            return w[-1]
        else: 
            return None
    if sum(ls[:k]) > t:
        return None
    las_sum = sum(ls[-k:])
    if las_sum < t:
        return las_sum
    
    r = None
    for i in range(1, len(ls) - k + 2):        
        val = ls[-i]
        if val > t:
            continue  
        
        l = ls[:]
        del l[-i]
        result = _choose_best_sum(t-val, k-1, l)
        if result is not None:
            if r is not None:
                r = max(r, result + val)
            else:
                r = result + val
    if r is not None:
        return r
    return None

from itertools import combinations

def choose_best_sum(t, k, ls):
    ks = list(range(len(ls)))
    
    c = list(combinations(ks, k))
    
    best = 0
    
    for choice in c:
        s = sum(ls[d] for d in choice)
        if not s > t and s > best:
            best = s
    
    return best or None
    
    


def choose_best_sum(t, k, ls):
    import itertools

    best = 0

    candidates = list(itertools.combinations(ls, k))

    for candidate in candidates:
        if sum(candidate) <= t and sum(candidate) > best:
            best = sum(candidate)

        else:
            continue

    if best == 0:
        return None

    else:
        return best



import itertools
def choose_best_sum(t, k, ls):
    p=list(ls)
    a=itertools.combinations(p,k)
    x=0
    c=0
    p.sort()
    if k>len(ls):
        return None
    for i in range(k):
        c=c+p[i]
        if i+1==len(ls):
            break
    if c>t:
        return None
    for i in a:
        if sum(i)<=t and ((t-sum(i)) < (t-x)):
            x=sum(i)
    return x

    
    


def choose_best_sum(t, k, ls):
    import itertools
    combinations = [sum(i) for i in itertools.combinations(ls,k) if sum(i) <= t]
    if len(combinations) == 0:
        return None
    return max(combinations)

import itertools
def choose_best_sum(t, k, ls):
    # your codep
    print(t, k, ls)
    posible_roads = itertools.combinations(ls, k)
    under_posible = []
    for posibility in posible_roads:
#         print(sum(posibility))
        if sum(posibility) == t:
            return t
        elif sum(posibility) <= t:
            under_posible.append(sum(posibility))
    return sorted(under_posible)[-1] if under_posible else None
    print(sorted(under_posible))

def choose_best_sum(t, k, ls):
    from itertools import combinations
    ls_ = [sum(x) for x in [*combinations(ls, k)] if sum(x) <= t]
    if len(ls_) == 0:
        return None
    else:
        return max(ls_)


from itertools import combinations

def choose_best_sum(t, k, ls):
    l = [i for i in ls if i<=t]
    print(t, k, ls, l)
    try:
        return sorted([sum(i) for i in combinations(l, k) if sum(i)<=t])[-1]
    except:
        return None

from itertools import combinations 

def choose_best_sum(t, k, ls):
    uniqueCombinations = list(combinations(ls, k))
    
    sumOfCombos = []
    for tup in uniqueCombinations:
        tupSum = sum(list(tup))
        
        if tupSum <= t:
            sumOfCombos.append(tupSum)
    if len(sumOfCombos) == 0:
        return None
    else:
        return min(sumOfCombos, key=lambda x:abs(x-t))


from itertools import combinations

def choose_best_sum(t, k, ls):
    sum_list = list(set(sum(i) for i in combinations(ls, k)))
    best = [9999999999, 0]
    for i in sum_list:
        if t - i >= 0 and t - i < best[0]:
            best[0], best[1] = t - i, i 
    if best[1] == 0:
        return None
    else:
        return best[1]

from itertools import combinations

def choose_best_sum(t, k, ls):
    if len(ls)<k:
        return None
    best_sum = max([sum(c) if sum(c)<=t else 0 for c in combinations(ls, k)])
    return best_sum if best_sum else None


import itertools


def choose_best_sum(t, k, ls):
#     for i in itertools.combinations(ls,k):
#         print(i)
    try: 
        return max(sum(i) for i in itertools.combinations(ls,k) if sum(i)<=t)
    except:
        return None

from itertools import combinations
from operator import gt

def choose_best_sum(max_, count, distances):
    sums = list(filter(max_.__ge__, list(map(sum, combinations(distances, count)))))
    return max(sums) if sums else None


def choose_best_sum(t, k, ls):
    import itertools
    
    sumList = []
    c = list(itertools.combinations(ls, k)) #find all combinations without repetition
    mySet = set(c) #store combinations in unordered set

    for i in mySet:
        currentSum = sum(i)
        if currentSum <= t:
            sumList.append(currentSum) #appends list if sum being iterated is less than or equal to limit
    
    if len(sumList) == 0:
        return None #checks if there are any possible sums
    else:
        return max(sumList) #returns greatest possible sum within given arguments


def choose_best_sum(t, k, ls):
    from itertools import combinations

    i = [sum(a) for a in list(combinations(ls,k))]
    i.sort()
    result = None
    for a in i:
        if a <= t:
            result = a
    return(result)

combinationTotals = []

def choose_best_sum(t, k, ls):
    combinationTotals.clear()
    # your code
    ls.sort()
    total = 0

    if k > len(ls) or sum(ls[:k]) > t:
        return None
        
    combine_segments(k, ls, [], t)
    combinationTotals.sort()
    return combinationTotals[-1]

def combine_segments(k, ls, arr, t):
    for i in range(len(ls)-k+1):
        
        arr.append(ls[i])
        
        if k == 1:
            total = sum(arr)
            if total < t:
                combinationTotals.append(total)
            elif total == t:
                print(arr)
                combinationTotals.append(total)
                return t
            else:
                arr.pop()
                break
        else:
            if(combine_segments(k-1, ls[i+1:], arr, t) != None):
                return t
            
        arr.pop()
            
    return None

def choose_best_sum(t, k, ls):
    
    from itertools import combinations
    
    c = [i for i in combinations(ls, k)]
    l = []
    
    for i in c:
        l.append(sum(i))
    
    return max(list(filter(lambda x: x <= t, l)), default = None)

def choose_best_sum(t, k, ls):
    
    from itertools import combinations
    
    c = [i for i in combinations(ls, k)]
    l = []
    
    for i in c:
        l.append(sum(i))
        
    f = list(filter(lambda x: x <= t, l))
    
    return None if len(f) == 0 else max(f)

def choose_best_sum(t, k, ls):
    from itertools import combinations
    try:
        return max(s for s in map(sum, combinations(ls, k)) if s <= t)
    except ValueError:
        return None

from itertools import combinations

def choose_best_sum(t, k, ls):
    routes = combinations(ls, k)
    sums = sorted([x for x in list(map(sum, routes)) if x <= t])
    if sums: return sums[-1]
    


from itertools import combinations

def choose_best_sum(t, k, ls):
    try:
         return min((abs(sum(x) - t), sum(x)) for x in combinations(ls, k) if sum(x) - t <= 0)[1]
    except ValueError:
        return None

from itertools import combinations

def choose_best_sum(t, k, ls):
    tp = []
    for m in combinations(ls, k):
        if sum(m) <= t:
            if sum(m) == t: return sum(m)
            tp.append(sum(m))
    return max(tp) if len(tp) > 0 else None


best_sums = {}
def choose_best_sum(t, k, ls):
  ls = [x for x in ls if x <= t]
  if k > len(ls):
    return None
  if k == 1:
    best_sum= max(ls)
    return best_sum
  ls.sort()
  the_tuple= tuple([t]+[k]+ls)
  best_sum = best_sums.get(the_tuple)
  if best_sum is not None:
    return best_sum
  else:
    i= 0
    best_sum = None
    while i < len(ls):
      nt = t-ls[i]
      s = choose_best_sum(nt, k-1, ls[0:i]+ls[i+1:])
      if s is None:
        del ls[i]
        continue
      else:
        best_sum = max(0 if best_sum is None else best_sum, s+ls[i])
        if best_sum == t:
          best_sums[the_tuple]= best_sum
          return best_sum
      i += 1
  if best_sum is not None:
    best_sums[the_tuple]= best_sum
  return best_sum

from itertools import combinations

def choose_best_sum(t, k, ls):
    a = sorted([sum(i) for i in combinations(ls, k)])
    for i in a[::-1]:
        if i <= t:
            return i
    return None

import itertools
def choose_best_sum(t, k, ls):
    n = itertools.combinations(ls,k)
    try: return max([sum(i) for i in n if sum(i) <= t])
    except: return None

import itertools


def choose_best_sum(t, k, ls):
    result = [sum(seq) for seq in itertools.combinations(ls, k) if sum(seq) <= t]
    if len(result) == 0:
        return None
    else:
        return max(result)

from itertools import combinations

def choose_best_sum(t, k, ls):
    return max((sum(i) for i in combinations(ls,k) if sum(i)<= t), default=None)
    
        
            
        
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
#     arr=[]
#     for index, num in enumerate(ls):
#         while index+k-1 <= len(ls)-1:
#             totalSum = 0
#             totalSum = sum(ls[index+1:index+k-1],num)
#             if totalSum < t:
#                 arr.append(totalSum)
#             index +=1
#             print(index,num,totalSum,)
    
#     arr.sort()
#     print(arr)
#     if arr !=[]:
#         return arr[-1]