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.math.*;

// **** D. Yet Another Subarray Problem ****

public class D {
	static char [] in = new char [1000000];
	public static void main (String [] arg) throws Throwable {
		int n = nextInt();
		int m = nextInt();
		int k = nextInt();
		long [] a = new long [n];
		for (int i =0; i<n; ++i) a[i] = nextInt();
		
		long [][] dp = new long [m+1][n];
		for (int i = 0; i<dp.length; ++i) Arrays.fill(dp[i], Integer.MIN_VALUE);
		long best = Math.max(0, a[0] - k);
		dp[0][0] = 0;
		dp[1][0] = a[0] - k;
		
		for (int i = 1; i<n; ++i) {
			for (int len = 1; len <= m; ++len) dp[len][i] = dp[len-1][i-1] + a[i];
			dp[1][i] -= k;
			dp[0][i] = Math.max(0, dp[m][i]);
			
			for (int j = 0; j<=m;++j) best = Math.max(dp[j][i] , best);
		}
		System.out.println(best);
		
	}

	
	
	
	
	
	
	
	
	
	
	
	
	
	/************** HELPER CLASSES ***************/
    //static class HS extends HashSet<Integer>{public HS(){super();}public HS(int a){super(a);}};
	//static class AL extends ArrayList<Integer>{public AL(){super();}public AL(int a){super (a);}};
	static class Pair implements Comparable<Pair> {
		int i,j;long L; public Pair(int xx, int yy, long LL){i=xx;j=yy;L=LL;} 
		public int compareTo(Pair p) { return (this.L < p.L) ? -1 : ((this.L == p.L && this.i < p.i) ? -1 : 1);}
	}
	/************** FAST IO CODE FOLLOWS *****************/
	public static long nextLong() throws Throwable {
		long i = System.in.read();boolean neg = false;while (i < 33) i = System.in.read();if (i == 45) {neg=true;i=48;}i = i - 48;
		int j = System.in.read();while (j > 32) {i*=10;i+=j-48;j = System.in.read();}return (neg) ? -i : i;
	}
	public static int nextInt() throws Throwable {return (int)nextLong();}
	public static String next() throws Throwable {
		int i = 0; while (i < 33 && i != -1) i = System.in.read(); int cptr = 0; while (i >= 33) { in[cptr++] = (char)i; i = System.in.read();}
		return new String(in, 0,cptr);
	}
	/**** LIBRARIES ****/
	public static long gcdL(long a, long b) {while (b != 0) {long tmp = b;b = (a % b);a = tmp;}return a;}
	public static int gcd(int a, int b) {while (b != 0) {int tmp = b;b = (a % b);a = tmp;}return a;}
	public static int[] sieve(int LIM) {
		int i,count = 0;
		boolean [] b = new boolean [LIM];
		for (i = 2;i<LIM; ++i) if (!b[i]) {count++; for (int j = i<<1; j<LIM; j+=i) b[j] = true;}
		int [] primes = new int[count];
		for (i = 2,count=0;i<LIM;++i) if (!b[i]) primes[count++] = i;
		return primes;
	}
	public static int[] numPrimeFactors(int LIM) {
		int i,count = 0;
		int [] b = new int [LIM];
		for (i = 2;i<LIM; ++i) if (b[i] == 0) {count++; for (int j = i; j<LIM; j+=i) b[j]++;}
		return b;
	}
	public static StringBuilder stringFromArray(int [] a) {
		StringBuilder b = new StringBuilder(9*a.length);
		for (int i = 0; i<a.length; ++i) {
			if (i != 0) b = b.append(' ');
			b = b.append(a[i]);
		}
		return b;
	}
	public static long modPow (long a, long n, long MOD) { long S = 1; for (;n > 0; n>>=1, a=(a*a)%MOD) if ((n & 1) != 0) S = (a*S) % MOD; return S;}
}

/* Full Problem Text:
  
You are given an array a_1, a_2, \dots , a_n and two integers m and k.
You can choose some subarray a_l, a_{l+1}, \dots, a_{r-1}, a_r.
The cost of subarray a_l, a_{l+1}, \dots, a_{r-1}, a_r is equal to \sum\limits_{i=l}^{r} a_i - k \lceil \frac{r - l + 1}{m} \rceil, where \lceil x \rceil 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 \dots a_3: 15 - k \lceil \frac{1}{3} \rceil = 15 - 10 = 5; 
 a_3 \dots a_4: (15 - 3) - k \lceil \frac{2}{3} \rceil = 12 - 10 = 2; 
 a_3 \dots a_5: (15 - 3 + 4) - k \lceil \frac{3}{3} \rceil = 16 - 10 = 6; 
 a_3 \dots a_6: (15 - 3 + 4 + 8) - k \lceil \frac{4}{3} \rceil = 24 - 20 = 4; 
 a_3 \dots a_7: (15 - 3 + 4 + 8 + 3) - k \lceil \frac{5}{3} \rceil = 27 - 20 = 7.
Your task is to find the maximum cost of some subarray (possibly empty) of array a.

 */