Introducere

Prietenul vostru Turing vă cere din nou ajutorul! Acesta își dorește un calculator cuantic pentru a calcula o sumă colosală, imposibilă pentru orice om. Momentan nu dispune de resursele materiale și financiare pentru a lucra la nivel cuantic, așa că vă cere ajutorul!

Cerința

Se dă un șir cu N elemente, numere naturale și un număr natural K. Aveți la dispoziție următoarea operație care se poate folosi de maximum K ori: se aleg doi indici i si j pentru care i % k = j % k (1 ≤ i < j ≤ N) și se interschimbă valorile acestor doi indici.

La final, după toate operațiile, trebuie să alegeți K elemente consecutive, iar suma acestor K elemente reprezinta scorul vostru. Turing trebuie sa obtina suma maximă și vă roagă să-l ajutați!

Date de intrare

Prima linie contine un numar T, reprezentand numarul de teste. Fiecare test contine două linii.

Prima linie conține numerele N și K (1 ≤ K ≤ N ≤ 1000), N fiind numărul de elemente al șirului și K numărul prezentat în cerință.

A doua linie conține N numere întregi A₁, A₂, … , A_n ( 0 ≤ A_i ≤ 1000 ), șirul de N numere naturale.

Date de ieșire

Programul va afișa pe câte un rând nou suma maximă pentru fiecare dintre cele T operații.

Restricții și precizări

1 ≤ T ≤ 1000
1 ≤ K ≤ N ≤ 1000
0 ≤ A[i] ≤ 1000

Exemplu:

Intrare

5
3 2
5 6 0
1 1
7
5 3
7 0 4 0 4
4 2
2 7 3 4
3 3
1000000000 1000000000 999999997

Ieșire

Explicație

În primul caz, putem obține suma maximă 11 dacă alegem A₁, A₂ fără să efectuăm nicio operație.

În al treilea caz, putem obține suma maximă 15 dacă interschimbăm A₁ cu A₄, iar suma finală este alcatuită din elementele A₃, A₄, A₅.

Încărcare soluție

Lipește codul aici

1

def sume():

import sys

T, N, K = map(int, sys.stdin.readline().split())

A = list(map(int, sys.stdin.readline().split()))

B = [0] * K

for i in range(1, N+1):

    B[i % K] = max(B[i % K], A[i])

ans = sum(B)

print(ans)