#include <bits/stdc++.h>

using namespace std;
#include "peru.h"
long long seg[2500001*4+1];
long long mod = 1000000007;
void update(int p,int l,int r,int idx,int val){
    if(l==r){
        seg[p] = val;
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx,val);
    else update(p*2+1,md+1,r,idx,val);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
long long query(int p,int l,int r,int lq,int rq){
    if(l>=lq&&r<=rq)return seg[p];
    if(r<lq||l>rq)return 1e18;
    int md = (l+r)/2;
    return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
int solve(int n, int k,vector<int> ss){
    long long arr[n+1];
    for(int i = 1;i<=(n+1)*4;i++)seg[i] = 1e18;
    for(int i = 1;i<=n;i++)arr[i] = ss[i-1];
    long long a3[n+1] = {0};
    for(int i = 1;i<=n;i++){
        long long mi = arr[i];a3[i] = 1e18;
        for(int j = i-1;j>=max(0,i-k);j--){
            a3[i] = min(a3[i],a3[j]+mi);
            mi = max(mi,arr[j]);
        }
    }
    long long ans2 = 0 , po2 = 1;
    for(int i = n;i>=1;i--){
        ans2+=((a3[i]%mod)*po2)%mod;ans2%=mod;
        po2*=23;po2%=mod;
    }
    long long dp[n+1] = {0};
    update(1,0,n,0,0);
    multiset<long long> s;
    deque<pair<long long,long long>> st;
    for(int i = 1;i<=n;i++){
        long long mi = dp[i-1];
        while(!st.empty()&&arr[st.back().second]<=arr[i]){
            s.erase(s.lower_bound(st.back().first+arr[st.back().second]));
            mi = min(mi,st.back().first);
            st.pop_back();
        }
        st.push_back({mi,i});
        s.insert(mi+arr[i]);
        int la = 0;
        while(!st.empty()&&st[0].second<=i-k){
            la = st[0].second;
            s.erase(s.lower_bound(arr[st[0].second]+st[0].first));
            st.pop_front();
        }
        if(la<i-k){
        int e = st[0].second;
        s.erase(s.lower_bound(arr[e]+st[0].first));
        st.pop_front();
        long long vl = query(1,0,n,i-k,e-1);
        s.insert(arr[e]+vl);
        st.push_front({vl,e});
        }
        dp[i] =(*s.begin());
        update(1,0,n,i,dp[i]);
    }
    long long ans = 0 , po = 1;
    for(int i = n;i>=1;i--){
        ans+=((dp[i]%mod)*po)%mod;ans%=mod;
        po*=23;po%=mod;
    }
    if(ans!=ans2)assert(0);
    return ans;
}

implementer.cpp: In function ‘char nextch()’:
implementer.cpp:15:31: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |     if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos = 0;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccvhOAzu.o: in function `main':
implementer.cpp:(.text.startup+0x151): undefined reference to `solve(int, int, int*)'
collect2: error: ld returned 1 exit status