Professor GukiZ is concerned about making his way to school, because massive piles of boxes are blocking his way. 

In total there are n piles of boxes, arranged in a line, from left to right, i-th pile (1 ≤ i ≤ n) containing ai boxes. Luckily, m students are willing to help GukiZ by removing all the boxes from his way. Students are working simultaneously. At time 0, all students are located left of the first pile. It takes one second for every student to move from this position to the first pile, and after that, every student must start performing sequence of two possible operations, each taking one second to complete. Possible operations are:

  1. If i ≠ n, move from pile i to pile i + 1;
  2. If pile located at the position of student is not empty, remove one box from it.



GukiZ's students aren't smart at all, so they need you to tell them how to remove boxes before professor comes (he is very impatient man, and doesn't want to wait). They ask you to calculate minumum time t in seconds for which they can remove all the boxes from GukiZ's way. Note that students can be positioned in any manner after t seconds, but all the boxes must be removed.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105), the number of piles of boxes and the number of GukiZ's students. 

The second line contains n integers a1, a2, ... an (0 ≤ ai ≤ 109) where ai represents the number of boxes on i-th pile. It's guaranteed that at least one pile of is non-empty.

Output

In a single line, print one number, minimum time needed to remove all the boxes in seconds.

Examples

Input

2 1
1 1


Output

4


Input

3 2
1 0 2


Output

5


Input

4 100
3 4 5 4


Output

5

Note

First sample: Student will first move to the first pile (1 second), then remove box from first pile (1 second), then move to the second pile (1 second) and finally remove the box from second pile (1 second).

Second sample: One of optimal solutions is to send one student to remove a box from the first pile and a box from the third pile, and send another student to remove a box from the third pile. Overall, 5 seconds.

Third sample: With a lot of available students, send three of them to remove boxes from the first pile, four of them to remove boxes from the second pile, five of them to remove boxes from the third pile, and four of them to remove boxes from the fourth pile. Process will be over in 5 seconds, when removing the boxes from the last pile is finished.
import java.util.*;
import java.io.*;
import java.math.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
public class Tester {
	public static int[] dis;
	public static int[] color;
	static Queue<Integer> q=new LinkedList();
	//static int arr[];;
	public static void main(String args[])
	{
		InputReader in = new InputReader(System.in);
		OutputStream outputStream = System.out;
		PrintWriter out = new PrintWriter(outputStream);
		int n=in.nextInt(),m=in.nextInt();
		int arr[]=new int[n];
		for(int i=0;i<n;i++)
		{
			arr[i]=in.nextInt();
		}
		long low=0;
		long high=(long)1e18;
		long mid=0;
		while(high-low>1)
		{
			mid=(low+high)/2;
			if(count(n-1,arr.clone(),m,mid)==true)
			{
				high=mid;
			}
			else
			{
				low=mid;
			}
		}
		out.println(high);
		out.close();
	}
	static boolean count(int n,int arr[],int students,long time)
	{
		int nc=n;
		for(int i=0;i<students;i++)
		{
			long tc=time;
			while(nc!=-1&&arr[nc]==0)
			{
				nc--;
			}
			if(tc<nc+1)
			{
				return false;
			}
			else
			{
				tc-=nc+1;
				while(nc!=-1&&tc>0)
				{
					if(tc>=arr[nc])
					{
						tc-=arr[nc];
						arr[nc]=0;
						nc--;
						continue;
					}
					else
					{
						arr[nc]=(int)(arr[nc]-tc);
						tc=0;
					}
				}
				while(nc!=-1 &&arr[nc]==0)
					nc--;
				if(nc==-1 && arr[0]==0)
					return true;
			}
		}
		return false;
	}
	static boolean bipartite(ArrayList<Integer>[] arr,int n)
	{
		q.add(n);
		while(!q.isEmpty())
		{
			int pop=q.poll();
			for(int i=0;i<arr[pop].size();i++)
			{
				if(color[arr[pop].get(i)]==-1)
				{
					color[arr[pop].get(i)]=1-color[pop];
					q.add(arr[pop].get(i));
				}
				else
				{
					if(color[arr[pop].get(i)]==color[pop])
					{
						return false;
					}
				}
			}
		}
		return true;
	}
	static void run(int n,int k)
	{
		if(dis[n]==0)
		{
			q.add(n);
			dis[n]=k;
		}
		else
		{
			if(dis[n]>k)
				dis[n]=k;
		}
	}
	private static int[] nextIntArray(InputReader in,int n)	
	{
		int[] a=new int[n];
		for(int i=0;i<n;i++)
			a[i]=in.nextInt();
		return a;
	}
	public static double dis(double x1,double x2,double y1)
	{
		return Math.sqrt(((x1-x2)*(x1-x2))+(y1*y1));
	}
	private static String[] nextStringArray(InputReader in,int n)	
	{
		String[] a=new String[n];
		for(int i=0;i<n;i++)
			a[i]=in.next();
		return a;
	}
	private static void show(int[] a)
	{
		for(int i=0;i<a.length;i++)
			System.out.print(a[i]+" ");
		System.out.println();
	}
	private static void show2DArray(char[][] a)
	{
		for(int i=0;i<a.length;i++)
		{
			for(int j=0;j<a[0].length;j++)
				System.out.print(a[i][j]);
			System.out.println();
		}
	}
 static long fact(long x)
 {
	 long i=x,mul=1;
	 while(i>0)
	 {
		 mul=(mul%1000000007)*(i%1000000007)%1000000007;
		 i--;
	 }
	 return mul;
 }
 static class LengthComparator implements Comparator<String> {
	    public int compare(String arg0, String arg1) {
		// Use Integer.compare to compare the two Strings' lengths.
		return (arg0+arg1).compareTo(arg1+arg0);
	    }
	}
// static long output(ArrayList<Integer> h[],int j,boolean[] v)
// {
//	 int k;
//	 v[j]=true;
//	 sum++;
//	 for(k=0;k<h[j].size();k++)
//	 {
//		 if(v[h[j].get(k)]==false)
//		 {
//			 output(h,h[j].get(k),v);
//		 }
//	 }
//	 return sum;
// }
 static long func(boolean v[],int j,ArrayList<Integer> h[],long ban[])
 {
	 	v[j]=true;
	 	 int k;
	 	long sum=0;
	    sum=sum+ban[j];
	 	//System.out.println(h[j].size());
	 	for(k=0;k<h[j].size();k++)
	 	{
	 		if(v[h[j].get(k)]==false)
	 		{
	 			v[h[j].get(k)]=true;
	 			sum+=func(v,h[j].get(k),h,ban);
	 		}
	 	}
	 	return sum;
 }
/*static class Graph {
    	
    	private static Deque<Integer> stack = new ArrayDeque<Integer>();
 		private int least,count,v;
 		
		Set<Integer>[] cities;
    	private int[] risk;
    	
    	Graph(int n,String[] risk){
    		
    		cities = new HashSet[n];
    		this.risk = new int[n];
    		for(int i =0;i<n;i++){
    			cities[i] = new HashSet<>();
    		}
    		for(int i =0;i<n;i++){
    			this.risk[i] = Integer.parseInt(risk[i]);
    		}
    		visited = new boolean[n];
    	}
    	
    	
    	public void add(int x,int y){
    		cities[x].add(y);
    		cities[y].add(x);
    	}
}*/
	static int root(int arr[],int i)
	{
		while(arr[i]!=i)
		{
			i=arr[i];
		}
		return i;
	}
	static boolean find(int arr[],int a,int b)
	{
		if(root(arr,a)==root(arr,b))
		{
			return true;
		}
		else
			return false;
	}
	static void weighted_union(int arr[],int size[],int a,int b)
	{
		int root_a=root(arr,a);
		int root_b=root(arr,b);
		if(root_a!=root_b)
		{
			if(size[root_a]<size[root_b])
			{
				arr[root_a]=arr[root_b];
				size[root_b]+=size[root_a];
			}
			else
			{
				arr[root_b]=arr[root_a];
				size[root_a]+=size[root_b];
			}
		//	count--;
		}
	}
	static class Pair implements Comparable<Pair>
	{
		private long first;
		private long index;
		//private long second;;

		public Pair(long i, long j) 
		{ 
			this.first = i;
			this.index = j;
		}
		public long getFirst() { return first; }
		//public long getSecond() { return second; }
		public long getIndex() { return index ;}
		public void setFirst(long k) { this.first=k ; }
		public void setIndex(long k) { this.index=k ;}
		//public void setSecond(long k) { this.second=k ;}
		@Override
		public int compareTo(Pair o) 
		{
			return Long.compare(this.first, o.first);
		}
	}
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream inputstream) {
			reader = new BufferedReader(new InputStreamReader(inputstream));
			tokenizer = null;
		}

		public String nextLine(){
			String fullLine=null;
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					fullLine=reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				return fullLine;
			}
			return fullLine;
		}
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}

}