1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<string.h>
 5 #include<queue>
 6 #include<deque>
 7 #include<stack>
 8 #include<math.h>
 9 using namespace std;
10 typedef long long LL;
11 int ans[200005];
12 void RMQ(int n);
13 int mnsum[200005][22];
14 int mm[200005];
15 int rmq(int x, int y);
16 int  check(int n,int k,int s);
17 int main(void)
18 {
19     int n;
20     int  k;
21     while(scanf("%d %d",&n,&k),n>0&&k>0)
22     {
23         int i;
24         int sum = 0;
25         int minn = -1;
26         for(i = 1; i <= n; i++)
27         {
28             scanf("%d",&ans[i]);
29             sum += ans[i];
30         }
31         if(sum <= k)printf("-1\n");
32         else
33         {
34             RMQ(n);
35             for(i = 1; i <= sqrt(1.0*n); i++)
36             {
37                 int x = n/i;
38                 int xx = check(n,x,k);
39                 if(xx!=-1)
40                 {
41                     minn = xx;
42                     break;
43                 }
44             }
45             if(minn == -1)
46             {
47                 int y = n/(sqrt(1.0*n))-1;
48                 for(i = y; i >= 1; i--)
49                 {
50                     int xx = check(n,i,k);
51                     if(xx!=-1)
52                     {
53                         minn = xx;
54                         break;
55                     }
56                 }
57             }
58             printf("%d\n",minn);
59         }
60     }
61     return 0;
62 }
63 void RMQ(int n)
64 {
65     mm[0] = -1;
66     for(int i = 1; i<=n; i++)
67     {
68         mm[i] = ((i&(i-1)) == 0) ? mm[i-1]+1:mm[i-1];
69         mnsum[i][0] = ans[i];
70     }
71     for(int j = 1; j<=mm[n]; j++)
72         for(int i = 1; i+(1<<j)-1<=n; i++)
73             mnsum[i][j] = max(mnsum[i][j-1], mnsum[i+(1<<(j-1))][j-1]);
74 }
75 int rmq(int x, int y)
76 {
77     int k = mm[y-x+1];
78     return max(mnsum[x][k], mnsum[y-(1<<k)+1][k]);
79 }
80 int  check(int n,int k,int s)
81     {   //if(k==1)printf("1\n");
82         int sum = 0;
83         int i;
84         int cnt = 0;
85         for(i = 1; i+k-1<= n; i+=k)
86         {
87             cnt++;
88             sum += rmq(i,i+k-1);
89             if(sum > s)return cnt;//最小原则；
90         }
91         return -1;
92     }