Today you are going to lead a group of elven archers to defend the castle that is attacked by an army of angry orcs. Three sides of the castle are protected by impassable mountains and the remaining side is occupied by a long wall that is split into n sections. At this moment there are exactly ai archers located at the i-th section of this wall. You know that archer who stands at section i can shoot orcs that attack section located at distance not exceeding r, that is all such sections j that |i - j| ≤ r. In particular, r = 0 means that archers are only capable of shooting at orcs who attack section i.

Denote as defense level of section i the total number of archers who can shoot at the orcs attacking this section. Reliability of the defense plan is the minimum value of defense level of individual wall section.

There is a little time left till the attack so you can't redistribute archers that are already located at the wall. However, there is a reserve of k archers that you can distribute among wall sections in arbitrary way. You would like to achieve maximum possible reliability of the defence plan.

Input

The first line of the input contains three integers n, r and k (1 ≤ n ≤ 500 000, 0 ≤ r ≤ n, 0 ≤ k ≤ 1018) — the number of sections of the wall, the maximum distance to other section archers can still shoot and the number of archers yet to be distributed along the wall. The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109) — the current number of archers at each section.

Output

Print one integer — the maximum possible value of defense plan reliability, i.e. the maximum possible value of minimum defense level if we distribute k additional archers optimally.

Examples

Input

5 0 6
5 4 3 4 9


Output

5


Input

4 2 0
1 2 3 4


Output

6


Input

5 1 1
2 1 2 1 2


Output

3
import java.io.*;
import java.util.*;

public class G implements Runnable{
	public static void main (String[] args) {new Thread(null, new G(), "_cf", 1 << 28).start();}

	public void run() {
		JoltyScanner fs = new JoltyScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		int n = fs.nextInt();
		int r = fs.nextInt();
		long k = fs.nextLong();
		long[] a = new long[n];
		BIT bit = new BIT(n);
		for(int i = 0; i < n; i++) {
			a[i] = fs.nextLong();
		}

		long[] pre = new long[n];
		pre[0] = a[0];
		for(int i = 1; i < n; i++) pre[i] += pre[i-1] + a[i];
		long lo = 0, hi = (long)5e18, res = 0;
		for(int bs = 0; bs < 100 && lo <= hi; bs++) {
			long[] range = new long[n + 1];
			long mid = (lo + hi) >> 1L;
			long upd = 0, tk = k;
			for(int i = 0; i < n; i++) {
				upd += range[i];
				int left = Math.max(0, i - r);
				int right = Math.min(n-1, i + r);
				long sum = query(left, right, pre) + upd;
				
				if(sum < mid) {
					long need = mid - sum;
					tk -= need;
					upd += need; range[Math.min(right + r + 1, n)] -= need;
					if(tk < 0) break;
				}
			}
			
			if(tk < 0) {
				hi = mid - 1;
			}
			else {
				lo = mid + 1;
				res = mid;
			}
			
		}
		
		out.println(res);
		
		out.close();
	}
	
	long query(int left, int right, long[] p) {
		long res = p[right];
		if(left > 0) res -= p[left-1];
		return res;
	}
	
	class BIT {
		
		long[] bit;
		int n;
		
		public BIT(int a) {
			n = a + 1;
			bit = new long[n];
		}
		
		//Remember that when querying a sum to query the 1-based index of the value.
		
		void update (int index, long val) {
			while(index < n) {
				bit[index] += val;
				index += (index & (-index));
			}
		}
		
		long sum (int index) {
			long sum = 0;
			while(index > 0) {
				sum += bit[index];
				index -= (index & (-index));
			}
			return sum;
		}
		
		long query(int i, int j) {
			return sum(j) - sum(i-1);
		}
		
	}

	class JoltyScanner {
		public static final int BUFFER_SIZE = 1 << 16;
		public static final char NULL_CHAR = (char) -1;
		byte[] buffer = new byte[BUFFER_SIZE];
		int bufferIdx = 0, size = 0;
		char c = NULL_CHAR;
		BufferedInputStream in;
		public JoltyScanner(InputStream in) 
		{
			this.in = new BufferedInputStream(in, BUFFER_SIZE);
			c = nextChar();
		}
		public int nextInt() 
		{
			while(c < '0' || c > '9')
				c = nextChar();
			int res = 0;
			while(c >= '0' && c <= '9') {
				res = (res << 3) + (res << 1) + c - '0';
				c = nextChar();
			}
			return res;
		}
		
		public long nextLong() 
		{
			while(c < '0' || c > '9')
				c = nextChar();
			long res = 0;
			while(c >= '0' && c <= '9') {
				res = (res << 3L) + (res << 1L) + c - '0';
				c = nextChar();
			}
			return res;
		}
		
		public char nextChar() 
		{
			while (bufferIdx == size) 
			{
				try 
				{
					size = in.read(buffer);
				} catch (Exception e) 
				{
					return NULL_CHAR;
				}
				bufferIdx = 0;
			}
			return (char) buffer[bufferIdx++];
		}
	}


	void sort (int[] a) {
		int n = a.length;
		for(int i = 0; i < 50; i++) {
			Random r = new Random();
			int x = r.nextInt(n), y = r.nextInt(n);
			int temp = a[x];
			a[x] = a[y];
			a[y] = temp;
		}
		Arrays.sort(a);
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				//                br = new BufferedReader(new FileReader("testdata.out"));
				st = new StringTokenizer("");
			} catch (Exception e){e.printStackTrace();}
		}
		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
		public int nextInt() {return Integer.parseInt(next());}
		public long nextLong() {return Long.parseLong(next());}
		public double nextDouble() {return Double.parseDouble(next());}

		public String nextLine() {
			String line = "";
			try {line = br.readLine();}
			catch (Exception e) {e.printStackTrace();}
			return line;
		}
		public Integer[] nextIntegerArray(int n) {
			Integer[] a = new Integer[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public char[] nextCharArray() {return nextLine().toCharArray();}
	}

}