Оптимизировать код (не попадает в time-limit)

Сама задача:

Ограничение времени 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 — максимальную достижимую разность суммарной силы существ Хинаты и Кенмы.

Код:

t = int(input())
d = []

for _ in range(t):
    n, k = map(int, input().split())
    s = [int(a) for a in input().split()]
    ai2 = s[len(s) // 2:]
    ai1 = s[:len(s) // 2]
    k2=k-k//2

    for _ in range(k // 2):
        fuf1 = min(ai1)
        ai1.remove(fuf1)

    for _ in range(k2):
        fuf2 = max(ai2)
        ai2.remove(fuf2)

    D = sum(ai1) - sum(ai2)
    d.append(D)

print(*d, sep='\n')

Задача не проходит все тесты, не укладывается по времени. Где-то видел подсказку, что решается через "кучи", но не так разбираюсь в теме; не получается оптимизировать