Another Maximum Sum in Subarray
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Time Limit: 1.0 s
Memory Limit: 256.0 MB
Description
You are given an Array \(A[]\), length of the array is N. You need to find out largest subarray with length exactly K and sum is maximum.
For example, \(A[]\)= {3,5,6,2,4} and K=3,
all possible subarray from A[] with length K are,
{3,5,6},{5,6,2},{6,2,4}.
Before you find maximum subarray sum, you can do following operation as many times as you wish,
 Choose two indices i and j, if gcd of their value is greater than 1, gcd\((A[i],A[j]) > 1\) ,you can swap their elements. (ex. swap\((A[i],A[j])\))
gcd means greatest common divisor.
Example : gcd(4,6)=2, gcd(3,9)=3 ect.
Input
First Line, T number of test case.
In each test case,
First Line N and K.
Second Line an Array A[].
\(1<=T<=10^3\)
\(1<=N<=6 * 10^3\)
\(1<=K<=N\)
\(1<=A[]<=10^9\)
It is gurantee that sum of N overall test case does not exceed \(6 * 10^3\).
Output
In each test case, Print the maximum sum.
Sample
Input  Output 



First test case,
Intially Array \(A []\) = {1,6,3,6,2,7}; and K = 3.
If we choose indices 2 & 5, gcd(A[2],A[5])= gcd(6,2) = 2, which is greater than 1.
We can swap their value. After swap array look like,
\(A[]\) = {1,2,3,6,6,7}.
Now we can select subarray, 4 to 6, {6,6,7} and their sum is 19 which is maximum.
Brain Booster #4
 Status
 Done
 Rule
 ACM/ICPC
 Problem
 9
 Start at
 20240714 15:30
 End at
 20240714 19:00
 Duration
 3.5 hour(s)
 Host
 Partic.
 89