cf.java

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;

/* Name of the class has to be "Main" only if the class is public. */
class cf
{
    public static void main (String[] args) throws Exception
    {
        try
        {
            FastReader sc=new FastReader();
            StringBuffer buf=new StringBuffer();
            int t=sc.nextInt();
            for(int tc=0;tc<t;tc++)
            {
                int n=sc.nextInt();
                int mk=sc.nextInt();
                int a[]=new int[n];
                int b[]=new int[n];
                for(int i=0;i<n;i++)
                {
                    a[i]=sc.nextInt();
                    b[i]=a[i];
                }
                
//                while(c++<n)
//                {
                    int i=1,e=0;
                    while(i<n)
                    {
                        int c=0;
                        int f=e;
                        int l=e;
                        int j=f;
                        while(l<n && a[j]<a[l])
                        {
                            c++;
                            j++;
                            l++;
                        }
                        if(c>1)
                        {
                            int sum=0;
                            int co=0;
                            for(j=f;j<=l;j++)
                            {
                                sum=sum+a[j];
                                co++;
                            }
                            int r=0;
                            if(sum%r==0)
                                r=sum/co;
                            else
                                r=sum/co+1;
                            for(j=f;j<=l;j++)
                            {
                                if((a[j]-r)>mk)
                                {
                                    a[j]=a[j]-r-((a[j]-r)-mk);
                                }
                                else
                                {
                                    a[j]=r;
                                }
                            }
                            i=l+2;
                            e=l+1;
                        }
                        else
                        {
                            if(e<n && a[i]<a[e])
                            {
                                int d=Math.abs(a[e]-a[i]);
                                    d=d/2;

                                    int d1=0;
                                    if((b[e]-a[e])>=0)
                                    {
                                        d=Math.min(mk-(b[e]-a[e]), d);
                                        a[e]=a[e]-d;
                                        a[i]=a[i]+d;
                                        e++;
                                        i++;
                                    }
                                    else
                                    {
                                        if(a[e]>b[e])
                                        {
                                            d=Math.abs(a[e]-a[i]);
                                            d=d/2+1;
                                            d=Math.min(mk, d);
                                            d=Math.min(a[e]-b[e], d);
                                        }
                                        a[e]=a[e]-d;
                                        a[i]=a[i]+d;
                                        e++;
                                        i++;
                                    }

                            }
                            else
                            {
                                e++;
                                i++;
                            }
                        }
                    //}
                }
                int max=a[0];
                for(int j=0;j<n;j++)
                {
                    if(a[j]>max)
                        max=a[j];
                }
                System.out.print(max+"\n");
            }
            
            
        }
        catch(Exception e)
        {
            System.out.print(e);
        }
        
    }
    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;
        }
    }
}