ЕГЭ №27: максимальная сумма пары на расстоянии ≥ d, кратная K

Дан список целых чисел nums и числа d, k. Рассмотрим все пары индексов i < j, у которых расстояние между элементами не меньше d (то есть j - i >= d) и сумма nums[i] + nums[j] кратна k.

Функция max_pair_sum_div(nums, d, k) возвращает максимальную такую сумму. Если подходящей пары нет — вернуть None.

Требуется эффективное решение за O(n) (как в задании 27): идём слева направо и для каждого правого элемента nums[j] ищем ранее встреченный (уже разрешённый по расстоянию) элемент с остатком (k - nums[j] % k) % k, храня максимум по каждому остатку. Наивный перебор всех пар за O(n^2) использовать нельзя — но ответ обязан ему совпадать.

Вход: nums — список целых чисел; d >= 1; k >= 1. Выход: целое число (максимальная сумма) или None.

Примеры:

max_pair_sum_div([3, 1, 4, 1, 5, 9, 2, 6], 2, 3) -> 15
max_pair_sum_div([10, 20, 30, 40], 1, 10)        -> 70
max_pair_sum_div([1, 2, 3], 5, 2)                -> None