/*
    《用单调性优化动态规划》

    题意：将序列a[]划分成几部分，使得每部分的和不超过m，求各部分最大值之和最小
           i
    dp[i] = min{ dp[j] + max(j+1i) }
          j=b[i]-1   b[i]为满足sum[ji]<=m的最小的j，可用二分查找出来

   b[i]单调递增，即决策的区间[b[i],i]会递增，考虑用单调队列

   一个重要性质：
   对于一个最优决策dp[j]+max(j+1i) 必有a[j]>a[jj]    j<jj<=i
   例如：
         x  x+1  x+2  x+3  x+4  y
   a[] =  5  8    4   5    6   3
    y的可选择范围为[x,y]，即
    dp[x]+8 , dp[x+1]+6 , dp[x+2]+6 , dp[x+3]+6 , dp[x+4]+3
    由于dp[x]单调不减的，所以dp[x+1]+6相对于dp[x+2]dp[x+3]来说会更优
    也就是决策点处的a[k]值必须大于其之后的所有点！
    比它小的话，还不如退回去到某个k，a[k]>a[j]
    如上面的dp[x+2],dp[x+3]退到dp[x+1]

    所以在决策区间内维护一个单调下降的序列，缩小决策点的数目！！
    然后在这些决策点中选一个最小的，用bst可以logn
    最后，点beg-1也有可能称为决策点（但不在一开始的决策区间内），所以再加多这个


    维护成一个单调队列后，dp[j]+max(j+1..i)时是直接为dp[DQ[front]]+a[DQ[front+1]]
    很神奇，可能要往这方面想
    既然有优于O(n^2)的算法，必然能很快知道max(j+1..i)，如果是单调的话就是相邻的点了！

*/
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>

using namespace std;

const int MAXN = 100010;
const long long INF = 1LL<<50;

struct Node
{
    long long key;
    int size,pri;
    Node *ch[2];
};

struct Treap
{
    Node *root,*null;
    Node nodes[MAXN],*pN;
    
    void init()
    {
        pN = nodes;
        null = newNode(INF);
        null->ch[0] = null->ch[1] = null;
        null->size = 0;
        root = null;
    }
    void insert(long long key)
    {
        insert(root,newNode(key));
    }
    void erase(long long key)
    {
        erase(root,key);
    }
    Node *findKth(int k)
    {
        Node *tmp = findKth(root,k);
        return tmp!=null?tmp:NULL;
    }
    void print()
    {
        print(root);
        puts("");
    }


    Node *newNode(long long key)
    {
        pN->key = key;
        pN->pri = rand();
        pN->ch[0] = pN->ch[1] = null;
        pN->size = 1;
        return pN++;
    }
    void update(Node *&x)
    {
        if(x==null)return;//
        x->size = 1;
        x->size += x->ch[0]->size;
        x->size += x->ch[1]->size;
    }
    void rotate(Node *&x,int t)
    {
        Node *y = x->ch[t];
        x->ch[t] =y->ch[!t];
        y->ch[!t]=x;
        update(x);//
        x=y;
        update(y);
    }
    void insert(Node *&now,Node *x)
    {
        if(now==null)now = x;
        else
        {
            int t = x->key > now->key;
            insert(now->ch[t],x);
            if(now->ch[t]->pri > now->pri)rotate(now,t);
        }
        update(now);
    }
    Node *get(Node *x,Node *y)
    {
        return x!=null?x:y;
    }
    void erase(Node *&now,long long x)
    {
        if(now==null)return;
        if(now->key!=x)
        {
            int t = x > now->key;
            erase(now->ch[t],x);
        }
        else
        {
            if(now->ch[0]==null || now->ch[1]==null)now = get(now->ch[0],now->ch[1]);
            else 
            {
                int t = now->ch[1]->pri > now->ch[0]->pri;
                rotate(now,t);
                erase(now->ch[!t],x);
            }
        }
        update(now);
    }
    Node *Min()
    {
        Node *now=root;
        while(now->ch[0]!=null)now = now->ch[0];
        return now!=null?now:NULL;
    }
    Node *findKth(Node *now , int k)
    {
        if(k<=0 || k > now->size)return null;
        int lsize = now->ch[0]->size;
        if(k<=lsize)return findKth(now->ch[0] , k);
        if(k>lsize+1)return findKth(now->ch[1] , k - (lsize+1));
        return now;
    }
    void print(Node *x)
    {
        if(x==null)return;
        //printf("%lld %d %lld %lld\n",x->key,x->size,x->ch[0]->key,x->ch[1]->key);
        print(x->ch[0]);
        printf("%lld ",x->key);
        print(x->ch[1]);
    }
};


long long a[MAXN],sum[MAXN];
long long dp[MAXN];
long long n,m;
int DQ[MAXN];
Treap treap;

int bfind(int x)
{
    int low = 0,high = x;
    while(low<high)
    {
        int mid = (low+high)>>1;
        if(sum[x]-sum[mid-1]<=m)high = mid;
        else low = mid+1;
    }
    return high;
}
int main()
{
    //freopen("in","r",stdin);
    while(~scanf("%lld%lld",&n,&m))
    {
        bool flag = true;
        sum[0] = 0;
        a[0] = INF;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            sum[i] = sum[i-1]+a[i];
            if(a[i]>m)flag = false;
        }
        if(flag)
        {
            //         i
            //dp[i] = min{ dp[j]+max(j+1i) }
            //        j=beg[i]
            //DQ store pos of the discreasing sequence 
            //Treap stroe : dp[DQ[front]]+a[DQ[front+1]]
            int front = 0,tail = 0;
            dp[0] = 0;
            treap.init();
            for(int i=1;i<=n;i++)
            {
                int beg = bfind(i);
                while(front<tail&&DQ[front]<beg)
                {
                    if(front+1<tail)
                        treap.erase(dp[DQ[front]]+a[DQ[front+1]]);
                    front++;
                }
                while(front<tail&&a[DQ[tail-1]]<=a[i])//
                {
                    if(front<=tail-2)
                        treap.erase(dp[DQ[tail-2]]+a[DQ[tail-1]]);
                    tail--;
                }
                if(front<tail)
                {
                    //维护成一个单调队列后，直接这样子dp[DQ[tail-1]]+a[i]求即可！！
                    treap.insert(dp[DQ[tail-1]]+a[i]);
                }
                DQ[tail++] = i;
                dp[i] = dp[beg-1] + a[DQ[front]];
                Node *tmp = treap.Min();//单调队列存的是[beg..i]的可能最优决策点，用单调队列可以缩小决策范围！
                if(tmp)
                    dp[i] = min(dp[i],tmp->key);
            }
            printf("%lld\n",dp[n]);
        }
        else puts("-1");
    }
    return 0;
}


有O(n^2)的算法，多记录上一次的最优值p[i]，及那一段的最大值last
/*
    将一段序列分段，且每段之和不超过M，求使每段的最大值之和最小
    易想到
        dp[i]={dp[j-1]+Max(ji)}
    但要优化下：
    设last是dp[i]时的Max(ji),p[i]为取得最优值时的j
    1) sum[i+1]-sum[j-1]<=M
    如果x[i+1]<=last , 则dp[i+1]=dp[i],p[i+1]=p[i]
    否则，j=p[i]开始
    2) j=i开始找
*/
#include<cstdio>
#include<cstring>

const int MAXN=100010;
const __int64 inf=100000000000000LL;
__int64 dp[MAXN],sum[MAXN];
int x[MAXN],p[MAXN];

int main(){
    int N,flag=1;
    __int64 M;
    scanf("%d%I64d",&N,&M);
    sum[0]=0;
    for(int i=1;i<=N;i++){
        scanf("%d",&x[i]);
        if(x[i]>M)flag=0;
        if(flag)sum[i]=sum[i-1]+x[i];
    }
    if(!flag){printf("-1\n");return 0;}
    dp[0]=0;
    dp[1]=x[1],p[1]=1;//dp[i]= min(dp[j-1]+Max(ji))
    int last=x[1];//Max(j..i)
    for(int i=2,j,Max;i<=N;i++){
        dp[i]=inf;
        if(sum[i]-sum[p[i-1]-1]<=M){//优化
            if(x[i]<=last){
                dp[i]=dp[i-1];
                p[i]=p[i-1];
            }
            else{
                for(j=p[i-1],Max=x[i];j&&sum[i]-sum[j-1]<=M;j--){//j可以是p[i-1]
                    if(Max<x[j])Max=x[j];
                    if(dp[i]>dp[j-1]+Max){
                        dp[i]=dp[j-1]+Max;
                        p[i]=j;
                        last=Max;
                    }
                }
            }
        }
        else{
            //普通方程
            for(j=i,Max=x[i];j&&sum[i]-sum[j-1]<=M;j--){
                if(Max<x[j])Max=x[j];
                if(dp[i]>dp[j-1]+Max){
                    dp[i]=dp[j-1]+Max;
                    p[i]=j;
                    last=Max;
                }
            }
        }
    }
    printf("%I64d\n",dp[N]);
    return 0;
}