本人在wqs二分枚举斜率的时候，原本设置斜率边界是[-1000,1000],然后wa了，但是左边界改成-sum[n][n]就过了，这是为什么啊

#include <bits/stdc++.h>
#define pii pair<int,int>
#define il inline
#define ll long long
using namespace std;
const int N=4010;
const ll inf=1e18;
ll n,m;
ll mp[N][N];
ll cnt[N];
ll sum[N][N];
ll dp[N];
ll que[N];
ll ls[N],rs[N];
ll ANS;
ll cal(ll l,ll r)
{
    //l+1->r
    return sum[r][r]-sum[l][r]-sum[r][l]+sum[l][l];
}
ll gt(ll k,ll x,ll val)
{
    return dp[k]+cal(k,x)-val;
}
bool judge(ll x)
{
    ll hd=1,tl=0;
    que[++tl]=0;ls[0]=1,rs[0]=n;
    for(int i=1;i<=n;++i)
    {
        // cout<<i<<":"<<endl;
        // for(int i=hd;i<=tl;++i) cout<<que[i]<<" "<<ls[que[i]]<<" "<<rs[que[i]]<<endl;
        cnt[i]=0,ls[i]=rs[i]=0;
        while(hd<tl&&rs[que[hd]]<i) hd++;
        dp[i]=gt(que[hd],i,x);
        cnt[i]=cnt[que[hd]]+1;
        while(hd<tl&&gt(i,ls[que[tl]],x)<gt(que[tl],ls[que[tl]],x)) tl--;
        ll L=ls[que[tl]],R=n+1;
        while(L<=R)
        {
            ll mid=(L+R)>>1;
            if(gt(i,mid,x)<=gt(que[tl],mid,x)) R=mid-1;
            else L=mid+1;
        }
        // cout<<i<<" "<<que[tl]<<' '<<R+1<<" "<<gt(i,R+1,x)<<" "<<gt()
        ll p_ans=R+1;
        if(p_ans>n) continue;
        rs[que[tl]]=p_ans-1;
        que[++tl]=i;
        ls[i]=p_ans,rs[i]=n;
    }
    ANS=dp[n];
//     cout<<x<<" "<<cnt[n]<<" "<<ANS<<" "<<ANS+m*x<<endl;
    return cnt[n]>=m;
    //尽可能分多段，尽可能选靠后的点转移
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            cin>>mp[i][j];
            if(i>j) mp[i][j]=0;
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            sum[i][j]=sum[i][j-1]+sum[i-1][j]+mp[i][j]-sum[i-1][j-1];
        }
    }
    // for(int i=-15;i<=15;++i) judge(i);
    ll l=-sum[n][n],r=1000;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(judge(mid)) r=mid-1;
        else l=mid+1;
    }
    judge(r+1);
    // cout<<r+1<<endl;//
    cout<<ANS+m*(r+1)<<endl;
}
int main()
{
//     freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}