Всем привет. Кто поможет с задачей?(не получается попасть в лимит по времени)

Сама задача:

C. Тайное заклинание
Ограничение времени 1 секунда
Ограничение памяти 256Mb

Ввод
стандартный ввод или input.txt

Вывод
стандартный вывод или output.txt

Хината и Кенма играют в компьютерную игру. Для победы одному из них необходимо одолеть всех магических существ другого. Игру можно представить себе так: n существ выстроены в ряд, i-е существо обладает силой ai. Изначально все существа нейтральны, то есть не принадлежат ни Хинате, ни Кенме. Хината может выбрать ровно k существ и уничтожить их тайным заклинанием. После этого из оставшихся n−k существ первая половина (стоящие в начале ряда существа) переходит на сторону Хинаты, а вторая — на сторону Кенмы, после чего начинается бой. Хината очень хочет победить. Для этого ему необходимо максимизировать разность суммарной силы своих существ и существ Кенме, то есть величину D=(ai1+ai2+…+ai(n−k)∕2)−(ai(n−k)∕2+1+…+ain−k), где i1,…,in−k — позиции существ, оставшихся после использования Хинатой своей способности. Хината и Кенма собираются сыграть t игр. Помогите Хинате — для каждой игры найдите максимальное D, которого он может добиться.

Формат ввода
В первой строке входных данных задано единственное целое число t(1≤t≤10) — количество игр. Далее следуют t тестовых примеров, разделённых переводом строки. В первой строке каждого тестового примера через пробел заданы два целых числа n(2≤n≤3⋅10^5) и k(0≤k<n) — число существ и количество существ, которых Хината уничтожит. Обратите внимание, что Хината обязан использовать свою способность. Гарантируется, что n−k — чётное число. Во второй строке каждого тестового примера задано n целых чисел ai(1≤ai≤10^9) — силы существ.Гарантируется, что сумма n по всем t не превосходит 3⋅10^5.

Формат вывода
Для каждого тестового примера на отдельной строке выведите одно целое число D — максимальную достижимую разность суммарной силы существ Хинаты и Кенмы.

Вот мой код:

    for i in range(int(input())):
            nk = [int(i) for i in input().split()]
            tvary = [int(i) for i in input().split()]
            a = tvary[:len(tvary)//2]
            b = tvary[len(tvary)//2:]
            a.sort()
            b.sort()
            if nk[1] & 1:
                b = b[:-1]
                nk[1] -= 1
            for i in range(nk[1]//2): 
                b = b[:-1]
                a = a[1:]
            print(sum(a)-sum(b))

Как можно войти вовремя? Кто сможет подсказать?
(Нельзя использовать сторонние библиотеки.)