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`

Source: codewars | Difficulty: EASY
Tags: Fundamentals

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(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 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]


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))
	sums = [sum(i) for i in comb]
	try:
		return max([i for i in sums if i <= t])
	except:
		return None


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 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)


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
		elif 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):
	s = [sum(i) for i in list(combinations(ls, k)) if sum(i) <= t]
	return max(s) if s != [] else None


def potencia(ls):
	if len(ls) == 0:
		return [[]]
	r = potencia(ls[:-1])
	return r + [s + [ls[-1]] for s in r]

def combina(k, ls):
	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):
		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):
	combinations = itertools.combinations(ls, k)
	a = list(combinations)
	b = [sum(c) for c in a]
	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)
	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_


import itertools

def choose_best_sum(t, k, ls):
	if len(ls) < k:
		return None
	towns = [x for x in ls if x <= t]
	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


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):
	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)
		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):
	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)
	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


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):
	print(t, k, ls)
	posible_roads = itertools.combinations(ls, k)
	under_posible = []
	for posibility in posible_roads:
		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


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))
	mySet = set(c)
	for i in mySet:
		currentSum = sum(i)
		if currentSum <= t:
			sumList.append(currentSum)
	if len(sumList) == 0:
		return None
	else:
		return max(sumList)


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()
	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
		elif 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