# Участник:Andriygav/FP

Перейти к: навигация, поиск
```class my_string(str):
@staticmethod
def _my_lt(a, b):
if len(a) > len(b):
return False
elif len(a) < len(b):
return True
else:
if a > b:
return False
else:
return True
@staticmethod
def _my_gt(a, b):
if len(a) > len(b):
return True
elif len(a) < len(b):
return False
else:
if a > b:
return True
else:
return False

def _max(self, b):
if self._my_gt(self, b):
return self
else:
return b

def __lt__(self, b):
ab = self+b
ba = b+self
return self._my_lt(ab, ba)

def __gt__(self, b):
ab = self+b
ba = b+self
return self._my_gt(ab, ba)

def solver(n, k, a):
a_s = list(map(my_string, a))
a_s = sorted(a_s, reverse=True)

P = [["0" for _ in range(9)] for _ in range(k)]

a = list(map(int, a_s))

P[0][a[0] % 9] = str(a[0])

for i in range(1, n):
for j in range(k-1, 0, -1):
for q in range(9):
if P[j-1][q] != "0":
P[j][(q + a[i]) % 9] = my_string(P[j][(q + a[i]) % 9])._max(my_string(P[j-1][q] + str(a[i])))

if P[0][a[i] % 9] == "0" or my_string(a[i])._my_gt(my_string(a[i]), my_string(P[0][a[i] % 9])):
P[0][a[i] % 9] = str(a[i])

if P[k-1][0] == '0':
return '-1'
else:
return P[k-1][0]

t = int(input())