And here goes another problem on arrays. You are given positive integer len and array a which consists of n integers a1, a2, ..., an. Let's introduce two characteristics for the given array.

  * Let's consider an arbitrary interval of the array with length len, starting in position i. Value <image>, is the modular sum on the chosen interval. In other words, the modular sum is the sum of integers on the chosen interval with length len, taken in its absolute value.
  * Value <image> is the optimal sum of the array. In other words, the optimal sum of an array is the maximum of all modular sums on various intervals of array with length len. 



Your task is to calculate the optimal sum of the given array a. However, before you do the calculations, you are allowed to produce no more than k consecutive operations of the following form with this array: one operation means taking an arbitrary number from array ai and multiply it by -1. In other words, no more than k times you are allowed to take an arbitrary number ai from the array and replace it with  - ai. Each number of the array is allowed to choose an arbitrary number of times.

Your task is to calculate the maximum possible optimal sum of the array after at most k operations described above are completed.

Input

The first line contains two integers n, len (1 ≤ len ≤ n ≤ 105) — the number of elements in the array and the length of the chosen subinterval of the array, correspondingly. 

The second line contains a sequence consisting of n integers a1, a2, ..., an (|ai| ≤ 109) — the original array. 

The third line contains a single integer k (0 ≤ k ≤ n) — the maximum allowed number of operations. 

All numbers in lines are separated by a single space.

Output

In a single line print the maximum possible optimal sum after no more than k acceptable operations are fulfilled. 

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Examples

Input

5 3
0 -2 3 -5 1
2


Output

10


Input

5 2
1 -3 -10 4 1
3


Output

14


Input

3 3
-2 -5 4
1


Output

11
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class OptimalSumMkII 
{
	static long[] a;
	static int n, k, len;
	static HashMap<Long, Integer> ghost; //already used up, so no need to be accounted to
	//when it goes out of range
	static HashMap<Long, Integer> outofrangerem;
	static HashMap<Long, Integer> outofrangeadd;
	static HashMap<Long, Integer> inremovable;
	static PriorityQueue<Long> addable, removable;
	static long r = 0;
	static boolean debug = false;
	static boolean secdeb = false;
	static boolean sec = false;
	
	static void doit()
	{
		if(sec)debug = secdeb;
		sec = true;
		addable = new PriorityQueue<Long>();
		removable = new PriorityQueue<Long>();
		inremovable = new HashMap<Long, Integer>();
		outofrangerem = new HashMap<Long, Integer>();
		outofrangeadd = new HashMap<Long, Integer>();
		int using = 0;
		//list of worst minuses we can still add to USE
		long sum = 0;
		
		for(int i = 0; i < n; i++)
		{
			sum += a[i];
			if(a[i] < 0)
			{
				addable.offer(a[i]);
			}
			
			if(i >= len)
			{
				int expi = i - len;
				sum -= a[expi];
				//index expi expires
				//so it becomes out of range,
				//unless it's already used up/eliminated (ghost)
				
				if(a[expi] < 0)
				{
					if(inremovable.containsKey(a[expi]*-1) && inremovable.get(a[expi]*-1) > 0)
					{
						inremovable.put(a[expi]*-1, inremovable.get(a[expi]*-1)-1);
						sum += a[expi]*2;
						using--;
						
						if(debug)System.out.println("Out of range rem " + a[expi]);
						if(outofrangerem.containsKey(a[expi]*-1))
						{
							outofrangerem.put(a[expi]*-1, outofrangerem.get(a[expi]*-1)+1);
						}
						else
						{
							outofrangerem.put(a[expi]*-1, 1);
						}
					}
					else
					{
						if(outofrangeadd.containsKey(a[expi]*-1))
						{
							outofrangeadd.put(a[expi]*-1, outofrangeadd.get(a[expi]*-1)+1);
						}
						else
						{
							outofrangeadd.put(a[expi]*-1, 1);
						}
					}
				}
			}
			
			boolean promotenewuses = true; //keep finding for addables to replace removables
			
			while(promotenewuses)
			{
				promotenewuses = false;
				if(debug)System.out.println("i = " + i + ", sum " + sum);
				
				 //GET BEST ADDABLE
				long newuse = 0; //negative
				
				{
					boolean found = false;
					if(!addable.isEmpty())
						newuse = addable.peek();
					else
						found = true; //no need to look for addables if there's none
					
					while(!found && !addable.isEmpty())
					{
						found = true;
						//outofrange: removed because out of range. so skip.
						if(outofrangeadd.containsKey(-newuse) && outofrangeadd.get(-newuse) > 0)
						{
							if(debug)System.out.println("Skip newuse " + (-newuse) + ": out of range");
							outofrangeadd.put(-newuse, outofrangeadd.get(-newuse)-1);
							addable.poll();
							if(addable.isEmpty()) 
								newuse = 0;
							else
								newuse = addable.peek();
								
							found = false;
						}
					}
				}
				 //GET BEST ADDABLE_END
				
				 //GET WORST REMOVABLE
				long min = 0;
				
				{
					boolean found = false;
					if(!removable.isEmpty())
						min = removable.peek();
					else
						found = true; //no need to look for removables if there's none
					
					while(!found && !removable.isEmpty())
					{
						found = true;
						//outofrange: removed because out of range. so skip.
						if(outofrangerem.containsKey(min) && outofrangerem.get(min) > 0)
						{
							if(debug)System.out.println(removable);
							if(debug)System.out.println("Skip min " + min + ": out of range");
							outofrangerem.put(min, outofrangerem.get(min)-1);
							removable.poll();
							if(removable.isEmpty()) 
								min = 0;
							else
								min = removable.peek();
								
							found = false;
						}
					}
				}
				 //GET WORST REMOVABLE_END

				if(debug)System.out.println("newuse " + newuse + " min " + min + ", using " + using + "/" + k);
				
				
				if(newuse != 0)
				{ 
					if(using < k)
					{ //ADD BEST ADDABLE IF SLOT IS AVAILABLE
						if(debug)System.out.println("Now using on " + (newuse));
						sum += -newuse*2;
						using++;
						addable.poll();
						removable.add(-newuse);
						
						if(inremovable.containsKey(-newuse))
							inremovable.put(-newuse, inremovable.get(-newuse)+1);
						else
							inremovable.put(-newuse, 1);
						if(debug)System.out.println("Record " + (-newuse) + " into inremovable: " + inremovable.get(-newuse));
						
						promotenewuses = true;
						
					}
					else if(k > 0)
					{ //IF NOT, SEE IF REPLACEMENT IS AVAILABLE
						if(-newuse > min)
						{
							addable.poll();
							removable.poll();
							
							//put min back into addable queue
							addable.offer(-min);
							//
							

							inremovable.put(min, inremovable.get(min)-1);
							
							removable.offer(-newuse);
							if(inremovable.containsKey(-newuse))
								inremovable.put(-newuse, inremovable.get(-newuse)+1);
							else
								inremovable.put(-newuse, 1);
							if(debug)System.out.println("[REPLACE] Record " + (-newuse) + " into inremovable: " + inremovable.get(-newuse));
							
							sum -= min*2;
							sum += -newuse*2;
							
							promotenewuses = true;
						}
						
						
					}
				}
			}
			
			
			if(i >= len-1)
			{
				if(debug)System.out.println("--> sum " + sum);
				r = Math.max(r, sum);
			}
			
		}
	}

	public static void main(String[] args) 
	{
		FastReader sc = new FastReader();
		
		n = sc.nextInt();
		len = sc.nextInt();
		
		a = new long[n];
		
		for(int i = 0; i < n; i++)
		{
			a[i] = sc.nextLong();
		}
		
		k = sc.nextInt();
		
		doit();
		for(int i = 0; i < n; i++)
		{
			a[i] = a[i]*-1;
		}
		doit();
		
		System.out.println(r);
	}
	
	 static class FastReader 
	    { 
	        BufferedReader br; 
	        StringTokenizer st; 
	  
	        public FastReader() 
	        { 
	            br = new BufferedReader(new
	                     InputStreamReader(System.in)); 
	        } 
	  
	        String next() 
	        { 
	            while (st == null || !st.hasMoreElements()) 
	            { 
	                try
	                { 
	                    st = new StringTokenizer(br.readLine()); 
	                } 
	                catch (IOException  e) 
	                { 
	                    e.printStackTrace(); 
	                } 
	            } 
	            return st.nextToken(); 
	        } 
	  
	        int nextInt() 
	        { 
	            return Integer.parseInt(next()); 
	        } 
	  
	        long nextLong() 
	        { 
	            return Long.parseLong(next()); 
	        } 
	  
	        double nextDouble() 
	        { 
	            return Double.parseDouble(next()); 
	        } 
	  
	        String nextLine() 
	        { 
	            String str = ""; 
	            try
	            { 
	                str = br.readLine(); 
	            } 
	            catch (IOException e) 
	            { 
	                e.printStackTrace(); 
	            } 
	            return str; 
	        } 
	    } 
}
