Enough is enough. Too many times it happened that Vasya forgot to dispose of garbage and his apartment stank afterwards. Now he wants to create a garbage disposal plan and stick to it.

For each of next n days Vasya knows a_i — number of units of garbage he will produce on the i-th day. Each unit of garbage must be disposed of either on the day it was produced or on the next day. Vasya disposes of garbage by putting it inside a bag and dropping the bag into a garbage container. Each bag can contain up to k units of garbage. It is allowed to compose and drop multiple bags into a garbage container in a single day.

Being economical, Vasya wants to use as few bags as possible. You are to compute the minimum number of bags Vasya needs to dispose of all of his garbage for the given n days. No garbage should be left after the n-th day.

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 2⋅10^5, 1 ≤ k ≤ 10^9) — number of days to consider and bag's capacity. The second line contains n space separated integers a_i (0 ≤ a_i ≤ 10^9) — the number of units of garbage produced on the i-th day.

Output

Output a single integer — the minimum number of bags Vasya needs to dispose of all garbage. Each unit of garbage should be disposed on the day it was produced or on the next day. No garbage can be left after the n-th day. In a day it is allowed to compose and drop multiple bags.

Examples

Input

3 2
3 2 1


Output

3


Input

5 1
1000000000 1000000000 1000000000 1000000000 1000000000


Output

5000000000


Input

3 2
1 0 1


Output

2


Input

4 4
2 8 4 1


Output

4
import java.util.*;
import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

     //--------------->>>>IF YOU ARE HERE FOR QUICKSORT HACK THEN SORRY NO HACK FOR YOU<<<-------------------

public class a{ 
     static int[] count,count1,count2;
     static Node[] nodes;
     static long[] arr;
     static int[] dp;
     static char[] ch,ch1;
     static long[] darr,farr;
     static char[][] mat,mat1;
     static long x,h;
     static long maxl;
     static double dec;
     static long mx = (long)1e9+7;
     static String s;
     static long minl;
     static int start_row;
     static int start_col;     
     static int end_row;     
     static int end_col;     
     static long mod = 998244353;
     // static int minl = -1;
     // static long n;
     static int n,n1,n2;
     static long a;
     static long b;
     static long c;
     static long d;
     static long y,z;
     static int m;
     static long k;
     static String[] str,str1;
     static Set<Integer> set,set1,set2;
     static SortedSet<Long> ss;
     static List<Integer> list,list1,list2,list3;
     static PriorityQueue<Long> pq,pq1;
     static LinkedList<Integer> ll;
     static Map<Integer,List<Integer>> map,map1;
     static StringBuilder sb,sb1,sb2;
     static int index;
     static int[] dx = {0,-1,0,1,-1,1,-1,1};
     static int[] dy = {-1,0,1,0,-1,-1,1,1};

     // public static void solve(){

     //    FastScanner sc = new FastScanner();
     //    // int t = sc.nextInt();
     //    int t = 1;
     //    for(int tt = 0 ; tt < t ; tt++){
     //        int n = sc.nextInt();
     //        int m = sc.nextInt();
     //        int prev = 0;

     //        for(int i = 0 ; i < n ; i++){
     //           int s = sc.nextInt();
     //           int e = sc.nextInt();
     //           if(s > prev){
     //                System.out.println("NO");
     //                return;
     //           }
     //            prev = Math.max(prev,e);
     //        }
     //        if(prev == m)
     //            System.out.println("YES");
     //        else
     //            System.out.println("NO");

     //        // System.out.println(sb);
     //    }
        
        
     // }

     //--------------->>>>IF YOU ARE HERE FOR QUICKSORT HACK THEN SORRY NO HACK FOR YOU<<<-------------------

     public static void solve(){

        long prev = 0;
        long bags = 0;

        for(int i = 0 ; i < n; i++){

            if(i == 0){
                bags += arr[i]/k;
                prev = arr[i]%k;
                continue;
            }

            if(prev > 0 && arr[i] + prev < k){
                bags += 1; 
                prev = 0;
                continue;
            }

            arr[i] += prev;
            bags += arr[i]/k;
            prev = arr[i]%k;

        }

        if(prev > 0)
            bags += 1;

        System.out.println(bags);

     }

     public static void main(String[] args) {

            FastScanner sc = new FastScanner();
            // Scanner sc = new Scanner(System.in);
            // int t = sc.nextInt();
            int t = 1;
            // int l = 1;
            while(t > 0){
                
                // n = sc.nextInt();
                // n = sc.nextLong();
                // a = sc.nextLong();
                // b = sc.nextLong();
                // c = sc.nextLong();
                // d = sc.nextLong();

                // x = sc.nextLong();
                // y = sc.nextLong();
                
                // n = sc.nextLong();
                n = sc.nextInt();
                // n1 = sc.nextInt();

                // m = sc.nextInt();

                k = sc.nextLong();
                // s = sc.next();

                // ch = sc.next().toCharArray();
                // ch1 = sc.next().toCharArray();

                arr = new long[n];
                for(int i = 0 ; i < n ; i++){
                    arr[i] = sc.nextLong();
                }
                // ch = sc.next().toCharArray();
                // // m = n;
                // darr = new long[m];
                // for(int i = 0 ; i < m ; i++){
                //     darr[i] = sc.nextLong();
                // }

                // farr = new int[n];
                // for(int i = 0; i < n ; i++){
                //     farr[i] = sc.nextInt();
                // }

                // mat = new int[n][n];
                // for(int i = 0 ; i < n ; i++){
                //     for(int j = 0 ;  j < n ; j++){
                //         mat[i][j] = sc.nextInt();
                //     }
                // }

                // mat = new char[n][m];
                // for(int i = 0 ; i < n ; i++){
                //     String s = sc.next();
                //     for(int j = 0 ; j < m ; j++){
                //         mat[i][j] = s.charAt(j);
                //     }
                // }

                // str = new String[n];
                // for(int i = 0 ; i < n ; i++)
                //     str[i] = sc.next();

                // nodes = new Node[n];
                // for(int i = 0 ; i < n ;i++)
                //     nodes[i] = new Node(sc.nextInt(),sc.nextInt());

                // System.out.println(solve()?"YES":"NO");
                 solve();       
                 // System.out.println(solve());
                 t -= 1;
            }

     }

    public static int log(long n){

         if(n == 0 || n == 1)
             return 0;

         if(n == 2)
             return 1;

         double num = Math.log(n);
         double den = Math.log(2);

         if(den == 0)
             return 0;

         return (int)(num/den);
     }

    public static boolean isPrime(long n) { 
    // Corner cases 
        if (n <= 1)  
            return false; 

        if (n <= 3)  
            return true; 
      
        // This is checked so that we can skip  
        // middle five numbers in below loop 
        if (n%2 == 0 || n%3 == 0) 
            return false; 
      
        for (int i=5; i*i<=n; i=i+6) 
            if (n%i == 0 || n%(i+2) == 0) 
               return false; 
      
        return true; 
    } 

     public static long gcd(long a,long b){

        if(b%a == 0){
            return a;
        }
        return gcd(b%a,a);

     }

     // public static void swap(int i,int j){
     //     long temp = arr[j];
     //     arr[j] = arr[i];
     //     arr[i] = temp;
     // } 

    static final Random random=new Random();
    
    static void ruffleSort(long[] a) {
        int n=a.length;//shuffle, then sort 
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n);
            long temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }

    static class Node{
        Integer first;
        Integer second;
        Node(Integer f,Integer s){
            this.first = f;
            this.second = s;
        }
    }

     static class FastScanner {

                BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
                StringTokenizer st=new StringTokenizer("");
                String next() {
                        while (!st.hasMoreTokens())
                                try {
                                        st=new StringTokenizer(br.readLine());
                                } catch (IOException e) {
                                        e.printStackTrace();
                                }
                        return st.nextToken();
                }
                
                int nextInt() {
                        return Integer.parseInt(next());
                }
                int[] readArray(int n) {
                        int[] a=new int[n];
                        for (int i=0; i<n; i++) a[i]=nextInt();
                        return a;
                }
                long nextLong() {
                        return Long.parseLong(next());
                }
        }

}