Since you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount.

You are given an array a of length n and an integer c.

The value of some array b of length k is the sum of its elements except for the smallest. For example, the value of the array [3, 1, 6, 5, 2] with c = 2 is 3 + 6 + 5 = 14.

Among all possible partitions of a into contiguous subarrays output the smallest possible sum of the values of these subarrays.

Input

The first line contains integers n and c (1 ≤ n, c ≤ 100 000).

The second line contains n integers a_i (1 ≤ a_i ≤ 10⁹) — elements of a.

Output

Output a single integer  — the smallest possible sum of values of these subarrays of some partition of a.

Example

Input

3 5 1 2 3

Output

6

Input

12 10 1 1 10 10 10 10 10 10 9 10 10 10

Output

92

Input

7 2 2 3 6 4 5 7 1

Output

17

Input

8 4 1 3 4 5 5 3 4 1

Output

23

Note

In the first example any partition yields 6 as the sum.

In the second example one of the optimal partitions is [1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10] with the values 2 and 90 respectively.

In the third example one of the optimal partitions is [2, 3], [6, 4, 5, 7], [1] with the values 3, 13 and 1 respectively.

In the fourth example one of the optimal partitions is [1], [3, 4, 5, 5, 3, 4], [1] with the values 1, 21 and 1 respectively.

 

做法：

一道dp

设dp[i]为前i个的最小答案

那么

dp[i] = min(dp[i-1] , dp[i-c] + sum[（a[ i-c+1] ), a[i] ] - min(a[i-c+1] , a[i] ) )

 

代码:

1 #include
       
         2 using namespace std; 3 #include
        
          4 #include
         
           5 #define read(x) scanf("%I64d",&x) 6 template
          
            7 class RMQ{ 8     public: 9      T* a;10      int t;11      T **mn;12      T maxn;13      int *log2;14      void SetMaxn(T *maxn){15         this->maxn=*maxn;16      }17      void SetMaxn(T maxn){18         this->maxn=maxn;19      }20      void Creat(T a[],int maxn){
     //建立一个最大为maxn的RMQ处理类 21           int k=1,p=0;22           log2=new int[maxn+10];23           for(int i=0;i<=maxn;i++)24               log2[i]=(i==0?-1:log2[i>>1]+1);25           while(k
           
            <= maxn;++i){39                      T sa=mn[i][j-1];40                     T sb=mn[i+(1<<(j-1))][j-1];41                      if(sa
            
              rr;59 LL n,c;60 LL a[100100];61 LL f[100100];62 LL s[100100];63 int main(){64 rr.SetMaxn(1e15);65 s[0]=0;66 memset(f,-1LL,sizeof(f));67 read(n);68 read(c);69 for(int i=1;i<=n;i++){70 read(a[i]);71 s[i] = s[i-1] + a[i]; 72 }73 a[0]=1e15;74 f[0]=0;75 rr.Creat(a,n+1);76 for(int i=1;i<=n;i++){77 f[i] = f[i-1] + a[i];78 LL zans = 1e15;79 if(i-c>=0)80 zans = f[i-c] + s[i] - s[i-c] - rr.Getx(i-c+1,i);81 if (f[i]>zans)82 f[i] = zans;83 // cout<
             <<" "<
              
               <