题目大意：有n种物品，Imp有k次魔法，每个物品有一个价值v与一个价格p，你每次可以选择一个物品买下来，Imp则可以用一次魔法把物品变没，直到某一次Imp没有用魔法，那么你就可以把这件物品带走，你的收益就是这个物品的价值减去所有你选的物品的价格,假设你和Imp都是最优策略，问最多的收益是多少 n<=150000 k<=9 v<=1000000 p<=1000000
首先你买的物品的价值是单调增的，如果有两个物品vi<=vj，你先买i再买j的最小收益是min(vi-pi,vj-pi-pj) ，但是如果你先买j再买i最小收益就是min(vj-pj,vi-pi-pj) ，因为vi-pi-pj比vi-pi与vj-pi-pj都小，所以min(vj-pj,vi-pi-pj)<=min(vi-pi,vj-pi-pj)，所以先买i再买j肯定不会变差。
于是我们先把物品按价值从小到大排序，于是就可以Dp了
设f[i][j]代表从第i~n个中选，Imp只用不超过j次魔法的最大收益
显然f[i][0]=max(f[i+1][0],v[i]-p[i]);
如果j不等于0时 先算正好用j次魔法的 首先你可以选择不买->f[i][j]=f[i+1][j]。 如果你选择了买，那么决定权就在Imp手上了，如果他用魔法那就是f[i+1][j-1]-p[i]，不用的话就直接是v[i]-p[i]（此时只用了0次魔法，但是也可以更新f[i][j]) 。最后再用f[i][j-1]来更新，代表没有用满j次魔法 综上f[i][j]=min(f[i][j-1],max(f[i+1][j],min(v[i]-p[i],f[i+1][j-1]-p[i])))
这样，最后的答案就是max(f[1][m],0) 因为也可以一个都不买
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=150011,inf=~0u>>2;
struct tg{int v,p;}e[maxn];
inline void read(int &x){
char ch=getchar();x=0;
while (!isdigit(ch)) ch=getchar();
for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}
int n,m;
void init(){
read(n); read(m);
for (int i=1;i<=n;++i) read(e[i].v),read(e[i].p);
}
inline bool cmp(tg a,tg b){return a.v<b.v;}
int f[maxn][15];
void work(){
sort(e+1,e+n+1,cmp); memset(f[n],200,sizeof(f[n])); f[n][0]=max(e[n].v-e[n].p,0);
for (int i=n-1;i>=1;--i){
f[i][0]=max(f[i+1][0],e[i].v-e[i].p);
for (int j=1;j<=m;++j)
f[i][j]=min(f[i][j-1],max(f[i+1][j],min(e[i].v-e[i].p,f[i+1][j-1]-e[i].p)));
}
cout<<max(f[1][m],0)<<endl;
}
int main(){
int T; read(T); while (T--) init(),work();
return 0;
}