You are given an array a_1, a_2, ... , a_n and two integers m and k.

You can choose some subarray a_l, a_{l+1}, ..., a_{r-1}, a_r. 

The cost of subarray a_l, a_{l+1}, ..., a_{r-1}, a_r is equal to ∑_{i=l}^{r} a_i - k ⌈ (r - l + 1)/(m) ⌉, where ⌈ x ⌉ is the least integer greater than or equal to x. 

The cost of empty subarray is equal to zero.

For example, if m = 3, k = 10 and a = [2, -4, 15, -3, 4, 8, 3], then the cost of some subarrays are:

  * a_3 ... a_3: 15 - k ⌈ 1/3 ⌉ = 15 - 10 = 5; 
  * a_3 ... a_4: (15 - 3) - k ⌈ 2/3 ⌉ = 12 - 10 = 2; 
  * a_3 ... a_5: (15 - 3 + 4) - k ⌈ 3/3 ⌉ = 16 - 10 = 6; 
  * a_3 ... a_6: (15 - 3 + 4 + 8) - k ⌈ 4/3 ⌉ = 24 - 20 = 4; 
  * a_3 ... a_7: (15 - 3 + 4 + 8 + 3) - k ⌈ 5/3 ⌉ = 27 - 20 = 7. 



Your task is to find the maximum cost of some subarray (possibly empty) of array a.

Input

The first line contains three integers n, m, and k (1 ≤ n ≤ 3 ⋅ 10^5, 1 ≤ m ≤ 10, 1 ≤ k ≤ 10^9).

The second line contains n integers a_1, a_2, ..., a_n (-10^9 ≤ a_i ≤ 10^9).

Output

Print the maximum cost of some subarray of array a.

Examples

Input


7 3 10
2 -4 15 -3 4 8 3


Output


7


Input


5 2 1000
-13 -4 -9 -20 -11


Output


0
/*
 * @author derrick20
 * Hmm tricky one
 * Key insights needed: Given the m constraint being less than 10,
 * we should immediately jump to the idea of grouping things based on that
 * Key observation: We'd naturally try to make sub problems based on the index of the final
 * part of a certain sub array. From that, we notice that the start point of the
 * subarray can be reused: if we found a good start point (the prefix sum to whose point
 * is low), then that start point is going to serve future sub arrays with farther back
 * end points well. (Unless we find a subarray sum who is so negative that it's better
 * than the current smallest prefix sum to a certain start point. This
 */
import java.io.*;
import java.util.*;

public class subarrayProblem {
    public static void main(String args[]) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        long inf = (long) 1e18;

        // Stores the minimum prefix sum from the start to the position so far visited in the for loop
        // with a specific remainder mod M. The remainder information is necessary for us to know
        // whether the ceiling of the range length / M might need to by 1 more  (in the case of there
        // being slightly extra in the difference, with the end having greater remainder than the start)
        // If anything else, the ceiling will be the same.
        long[] minSum = new long[M];
        // Everything default to 0. We will only update if we can find negative values,
        // since anything positive is useless and would squander our precious positive numbers!
        Arrays.fill(minSum, inf);
        // However, we have to remember we could always just have 0 sum
        minSum[0] = 0;

        long bestSum = 0;
        long prefixSum = 0;
        // Rather than going back through some array, we can just track the result in place while
        // sweeping. At each end point, we are determining if the total sum MINUS the minSum to
        // any index before is any bigger than our old result.
        for (int i = 1; i <= N; i++) {

            prefixSum += arr[i - 1];

            long totalValue = prefixSum - K * (long) (Math.ceil((double) i / M));
//            System.out.println("---------------------------");
//            System.out.println("Position: " + i+ " Sum: " + prefixSum + " Total Value: " + totalValue);
//            System.out.println(Arrays.toString(minSum));
            // Update our minSum for the current mod, if possible
            // This will likely happen if lots of negative values
            if (totalValue < minSum[i % M]) {
                minSum[i % M] = totalValue;
            }

            long bestRemoval = 0;
            for (int remainder = 0; remainder < M; remainder++) {
                // We must try all possible SMALLEST subtractable values
                // We were forced to store a bit more information: the remainder mod M
                // because there is a certain threshold where the ceiling rounds up an extra bit
                long removedValue = minSum[remainder];
                // This means the ceiling function will pull up one extra K, which was not accounted
                // for in our subtracting of two prefix sums.
                if (remainder < (i % M) && (remainder % M != 0)) {
                    // If the blocks are too far, the ceiling pulls up and leads
                    // to an under valuing
                    removedValue += K;
                } else if (remainder > (i % M) && (i % M == 0)) {
                    // If the blocks are too close, the ceiling on the subtracted block
                    // leads to an undervalued amount between
                    removedValue += K;
                }
                bestRemoval = Math.min(bestRemoval, removedValue);
//                System.out.println("remainder: " + remainder + " removed: " + removedValue);
            }
//            System.out.println(totalValue + " " + bestRemoval);
            bestSum = Math.max(bestSum, totalValue - bestRemoval);
        }
        out.println(bestSum);
        out.close();
    }

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        FastScanner(FileReader s) {
            br = new BufferedReader(s);
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    }
}
