Rezolvare PBinfo #4201

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 A1, A2, … , An ( 0 ≤ Ai ≤ 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

11
7
15
10
2999999997

Explicație

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

În al treilea caz, putem obține suma maximă 15 dacă interschimbăm A1 cu A4, iar suma finală este alcatuită din elementele A3, A4, A5.