这题似乎是有$O(n)$做法的。。。当然$O(n^2)$也能过就是了。
贪心不太好做。
~~其实是不会贪心~~
考虑一个最暴力的$dp$。设$f[n][m]$表示递推到第$n$项，剩余$m$颗子弹所需要耗费的子弹，与已经丢弃掉的子弹。
这个$dp$看似有$O(nk)$项，但是仔细分析一下，可以发现：对于一个状态$f[i][j]$，转移只有两种可能。要么用这$j$个子弹打完第$i$波怪物后，重新装弹；要么不重新装弹，继续使用剩下的子弹攻击。这样只会转移到$f[i+1][J]$与$f[i+1][K]$。$J$可以方便地计算出来。
所以每次递推只会多产生$1$种状态，总状态就是$O(n^2)$，复杂度$O(n^2logn)$。
```cpp
/*************************************************************************
> File Name: f.cpp
> Author: The-Out-Land
> Mail:
[email protected]
> Created Time: 2020年10月11日 星期日 16时52分34秒
************************************************************************/
#include <bits/stdc++.h>
#define enter putchar('\n')
#define space putchar(' ')
#define re register
#define N 2010
#define int long long
#define fi first
#define se second
using namespace std;
const int inf=0x1f3f3f3f3f3f3f3f;
inline int max(int x,int y){return (x>y?x:y);}
inline int min(int x,int y){return (x<y?x:y);}
inline int read(){
int x=0;char c=getchar();bool y=1;
for(;c<'0' || c>'9';c=getchar()) if(c=='-') y=0;
for(;c>='0' && c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-48;
if(y) return x;
return -x;
}
int n,K,cnt,pre,fans;
struct data{
int l,r,val;
data(const int X=0,const int Y=0,const int Z=0):l(X),r(Y),val(Z){}
}a[N],B;
map<int,int> f[N],Q;
bool cmp(const data &x,const data &y){return x.l==y.l?x.r<y.r:x.l<y.l;}
inline void Input(){
n=read(),K=read();
for(re int i=1;i<=n;++i){
B.l=read(),B.r=read(),B.val=read();
if(B.l==B.r) Q[B.l]+=B.val;
else a[++cnt]=B;
}
for(auto i:Q){
a[++cnt]=data(i.fi,i.fi,Q[i.fi]);
}
sort(a+1,a+cnt+1,cmp);
n=cnt;
return;
}
inline void solve(){
f[0][K]=0;
int now;
for(re int i=1;i<=n;++i){
pre=i-1;
f[i][K]=inf;
for(auto J:f[pre]){
int j=J.fi,V=J.se;
if(V==inf) continue;
if(j+(a[i].r-a[i].l)*K<a[i].val) continue;
if(j>=a[i].val){
if(f[i].find(j-a[i].val)==f[i].end())
f[i][j-a[i].val]=inf;
f[i][j-a[i].val]=min(f[i][j-a[i].val],V+a[i].val);
if(a[i+1].l!=a[i].l)
f[i][K]=min(f[i][K],V+j);
continue;
}
now=(K-(a[i].val-j)%K)%K;
if(f[i].find(now)==f[i].end()) f[i][now]=inf;
if(j+max(0ll,a[i].r-a[i].l-1)*K>=a[i].val || a[i+1].l!=a[i].r){
if(a[i+1].l!=a[i].l)
f[i][K]=min(f[i][K],V+now+a[i].val);
f[i][now]=min(f[i][now],V+a[i].val);
}
else{
f[i][now]=min(f[i][now],V+a[i].val);
}
}
/*printf("%lld\n",i);
for(auto J:f[i]) printf("%lld %lld\n",J.fi,J.se);*/
if(f[i].empty()) return puts("-1"),void();
pre=i;
}
fans=inf;
for(auto i:f[n]) fans=min(fans,f[n][i.fi]);
if(fans==inf) return puts("-1"),void();
cout<<fans<<endl;
return;
}
signed main(){
//freopen("data.in","r",stdin);
Input();
solve();
return 0;
}
```