Пат и паташон задача python

Я решаю задачу Боб придумал логическую игру "Пат и Паташон". В этой игре на виртуальной сцене находится n персонажей различного роста, которые выстроены в один ряд. Игрок может удалить часть персонажей со сцены, при этом оставшиеся персонажи смыкаются, не изменяя своего взаимного расположения. После этого персонажи на сцене разбиваются на пары: первый со вторым, третий с четвертым, пятый с шестым и так далее. В момент удаления игрок должен позаботится о том, чтобы количество оставшихся персонажей стало четным. Первого персонажа в паре (с нечетным номером) будем называть Патом, а второго (с четным номером) — Паташоном. Эффектностью пары будем назвать разность роста Пата и Паташона. Эффектность может быть отрицательной, если окажется, что Пат ниже, чем Паташон. За один раунд игрок получает количество очков, равное сумме эффектностей всех пар. Игрок может удалить со сцены всех персонажей. В этом случае он получит ноль очков.

Рассмотрим пример. Пусть на сцене изначально находилось девять персонажей, рост которых задается массивом чисел (120,160,180,160,120,110,150,170,100) (120,160,180,160,120,110,150,170,100). Игрок удалил со сцены первого второго и седьмого персонажа. На сцене осталось шесть персонажей с ростом (180,160,120,110,170,100) (180,160,120,110,170,100). Они разбились на три пары (180,160),(120,110),(170,100) (180,160),(120,110),(170,100);, при этом эффектность первой пары — 20, второй — 10, третей — 70. Таким образом, за такое разбиение на пары игрок получит 100 очков. Однако, если игрок оставит на сцене четырех персонажей с ростом (180,110,170,100) (180,110,170,100), то он получит 140 очков.

Напишите программу, которая посчитает максимальное количество очков, которые может получить игрок, для заданной последовательности персонажей.

Формат входных данных На вход в первой строке подается одно натуральное число n — количество персонажей на сцене в начале игры, 1≤n≤1000. Далее в одной строке через пробел записана последовательность из n натуральных чисел, которые задают рост персонажей. Числа не превосходят 1000. Формат выходных данных Выведите одно целое число — максимальное количество очков, которое может получить игрок для заданной последовательности персонажей.

Методика проверки Программа проверяется на 15 тестах. Прохождение каждого теста оценивается в 1 балл. Тест из условия задачи при проверке не используется. В первых пяти тестах на сцене изначально находится ровно четыре персонажа.

Sample Input: 9 120 160 180 160 120 110 150 170 100 Sample Output: 140 у меня получилось такое решение, но оно не проходит по времени

import itertools
n = int(input())
a = list(map(int,input().split()))
result = []
def summa(list1):
    count = 0
    for k in range(0,len(list1) - 1,2):
        count += (list1[k] - list1[k+1])
    return count

for i in range(2, n + 2, 2):
    pr = itertools.combinations(a,i)
    result.extend(list(map(summa,pr)))
print(max(result))