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
import java.util.*;
import java.io.*;

public class Solution
{
       static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                                 BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
    static int parent(int x , int p[])
    {
           if(p[x] == x)
           return x;
           
           return (p[x] = parent(p[x],p));
    }
    
    static void union(int a , int b , int p[] , int size[])
    {
           a = parent(a,p);
           b = parent(b,p);
           
           if(size[a] < size[b])
           {
                  int temp = a;
                  a = b;
                  b = temp;
           }
           p[b] = a;
           size[a] += size[b];
    }
    
   
  
  static int max(int x)
  {
         for(int j = 30 ; j >= 0 ; j--)
         {
                if((x&(1<<j)) > 0)
                return j;
         }
         return -1;
  }
  static void dfs(int n , LinkedList<Integer> arr[] , int p , int pp[])
  {
         pp[n] = p;
         for(Integer i : arr[n])
         {
                if(i != p)
                {
                       dfs(i,arr,n,pp);
                }
         }
  }
  
  static void dfs2(int n , LinkedList<Integer> arr[] , int p , int w[] , long dp[] , long max[])
  {
         long mx = 0;
         for(Integer i : arr[n])
         {
                if(i != p)
                {
                       dfs2(i,arr,n,w,dp,max);
                       dp[n] += dp[i]+2*w[i];
                       mx = Math.max(mx,w[i]+max[i]);   
                }
         }
         max[n] = mx;
  }
  
 static int getSum( int index , int BITree[])
{
    int sum = 0; // Iniialize result
  
    // index in BITree[] is 1 more than the index in arr[]
   // index = index + 1;
  
    // Traverse ancestors of BITree[index]
    while (index>0)
    {
        // Add current element of BITree to sum
        sum += BITree[index];
  
        // Move index to parent node in getSum View
        index -= index & (-index);
    }
    return sum;
}
  
// Updates a node in Binary Index Tree (BITree) at given index
// in BITree. The given value 'val' is added to BITree[i] and 
// all of its ancestors in tree.
static void updateBIT(int n, int index, int val , int BITree[])
{
    // index in BITree[] is 1 more than the index in arr[]
    //index = index + 1;
  
    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
    // Add 'val' to current node of BI Tree
    BITree[index] += val;
  
    // Update index to that of parent in update View
    index += index & (-index);
    }
}
static int max;
static long inv(int arr[])
{
       int n = arr.length;
       int bit[]  = new int[n+1];
       long ans = 0;
       for(int i = 0 ; i < n; i++)
       {
              updateBIT(n,arr[i],1,bit);
              ans += getSum(n,bit)-getSum(arr[i],bit);
       }
       return ans;
}


static void dfs(int n , int arr[] , LinkedList<Integer> g[] , HashMap<Integer,Integer> map[] , int prime[] , int p)
{
      HashMap<Integer,Integer> mx = new HashMap<Integer,Integer>(); 
       HashMap<Integer,Integer> nextmx = new HashMap<Integer,Integer>(); 
       
       int temp = arr[n];
       for(Integer i : g[n])
       {
              if(i != p)
              {
                     dfs(i,arr,g,map,prime,n);
                     for(Map.Entry entry : map[i].entrySet())
                     {
                            int k = (int)entry.getKey();
                            int v = (int)entry.getValue();
                            
                            if(arr[n]%k == 0)
                            {
                            if(!mx.containsKey(k))
                            mx.put(k,v);
                            
                            else if(!nextmx.containsKey(k))
                            {
                                 if(v >= mx.get(k))
                                 {
                                         nextmx.put(k,mx.get(k));
                                          mx.put(k,v);
                                 }
                                 
                                 else
                                 {
                                        nextmx.put(k,v);
                                 }
                            }
                            
                            
                            else
                            {
                                   if(v >= mx.get(k))
                                   {
                                          nextmx.put(k,mx.get(k));
                                          mx.put(k,v);
                                   }
                                   
                                   else if(v >= nextmx.get(k))
                                   nextmx.put(k,v);
                            }
                     }
              }
       }
}

while(temp > 1)
{
       int x = prime[temp];
       while(temp%x == 0)
       {
              temp = temp/x;
       }
      // int curr = 0;
       if(mx.containsKey(x))
       {
              max = Math.max(max,mx.get(x)+1);
              
              if(nextmx.containsKey(x))
              max = Math.max(max,mx.get(x)+nextmx.get(x)+1);
              
              map[n].put(x,mx.get(x)+1);
       }
       
       else
       {
       map[n].put(x,1);
       max = Math.max(max,1);
       }
}

}
//static int dp[][][];
/*static int merge(int l , int r , int side , int arr[])
{
       if(l == 0 && r == arr.length-1)
       return 0;
       
       if(dp[l][r][side] != -1)
       return dp[l][r][side];
       
       dp[l][r][side] = Integer.MAX_VALUE;
       int col = -1;
       if(side == 0)
       col = arr[l];
       
       else
       col = arr[r];
       
       if(l == 0)
       {
              if(col == arr[r+1])
              dp[l][r][side] = merge(l,r+1,1,arr);
              
              else
              dp[l][r][side] = 1+merge(l,r+1,1,arr);
       }
       
       else if(r == arr.length-1)
       {
          if(col == arr[l-1])
              dp[l][r][side] = merge(l-1,r,0,arr);
              
              else
              dp[l][r][side] = 1+merge(l-1,r,0,arr);    
       }
       
       else
       {
              if(col == arr[l-1])
              dp[l][r][side] = Math.min(dp[l][r][side],merge(l-1,r,0,arr));
              
              else
              dp[l][r][side] = Math.min(dp[l][r][side],1+merge(l-1,r,0,arr));
              
              
              
              if(col == arr[r+1])
              dp[l][r][side] = Math.min(dp[l][r][side],merge(l,r+1,1,arr));
              
              else
              dp[l][r][side] = Math.min(dp[l][r][side],1+merge(l,r+1,1,arr));
       }
       
       return dp[l][r][side];
       

}*/


  

       public static void main(String []args) throws IOException
       {
              Reader sc = new Reader();
              int n = sc.nextInt();
              int m = sc.nextInt();
              long k = sc.nextLong();
              long pre[] = new long[n+1];
              for(int i = 1  ; i <= n ; i++)
              {
                     long x = sc.nextLong();
                     pre[i] = pre[i-1]+x;
              }
              long up[] = new long[m];
              long down[] = new long[m];
              long ans = 0;
              for(int i = 1 ; i < m ; i++)
              {
                     up[i] = Long.MIN_VALUE;
                     down[i] = Long.MIN_VALUE;
              }
              for(int i = 1 ; i <= n ; i++)
              {
                     
                     long temp = pre[i];
                     if(i%m == 0)
                     temp -= (long)(i/m)*k;
                     
                     else
                     temp -= (long)((i/m)+1)*k;
                     
                     
                     
                     for(int j = 0 ; j < m ; j++)
                     {
                            if(j < i%m && down[j] != Long.MIN_VALUE)
                            ans = Math.max(ans,temp+down[j]);
                            
                            else if(j >= i%m && down[j] != Long.MIN_VALUE)
                           ans = Math.max(ans,pre[i]-(long)(i/m)*k+down[j]);
                     }
                     
                   
                    
                     
                     down[i%m] = Math.max(down[i%m],(long)(i/m)*k-pre[i]);
                     
                     up[i%m] = Math.max(up[i%m],-temp);
                     
                     
              }
              System.out.println(ans);
       }
}