考虑线段树分治。
线段树分治实际上就是将把时间按照线段树的方法分治下去。线段树的每个节点都是一个时间区间，预处理的时候如果一个操作的“存活时间”完全覆盖这个时间区间，就给这个时间区间打上标记并返回。然后在线段树上DFS，每次向下走到一个节点将这个节点的操作加入，离开时删除即可。
线段树分治大多数情况就是用来解决：加入某个元素之后删除这个元素很麻烦，但是按照插入的顺序从后到前“撤销”很方便。（类似栈的结构：只能弹出顶部，不能删除中间的。）
而这道题 是满足这个条件的。每次递归之前只需要把递归之前的状态复制一个“备份”。然后暴力的把“备份”还原即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=41000;
const int p=1e7+19;
const int q=1e9+7;
int ed[maxn],st[maxn];
pii item[maxn];
bool query[maxn];
int pro[maxn];
int k;
vi add[maxn*4];
void update(int l,int r,int rt,int tl,int tr,int node){
if(tl<=l&&r<=tr){
add[rt].pb(node);return;
}
int mid=(l+r)>>1;
if(tl<=mid)update(l,mid,rt<<1,tl,tr,node);
if(tr>=mid+1)update(mid+1,r,rt<<1|1,tl,tr,node);
}
ll ksm(ll num,ll t){
ll res=1;num%=q;
for(;t;t>>=1,num=num*num%q){
if(t&1)res=res*num%q;
}
return res;
}
int tmp[1005];
void solve(int l,int r,int rt){
int buc[1005]={0};
rep(i,0,(int)add[rt].size()-1){
int id=add[rt][i];
for(int j=k;j>=0;j--){
if(j+item[id].se<=k)tmp[j+item[id].se]=max(tmp[j+item[id].se],tmp[j]+item[id].fi);
}
}
if(l==r){
if(query[l]){
ll ans=0;
rep(m,1,k){
ans+=1ll*tmp[m]*pro[m-1]%q;ans%=q;
}
printf("%lld\n",ans);
}
return;
}
int mid=(l+r)>>1;
memcpy(buc,tmp,sizeof(tmp));
solve(l,mid,rt<<1);
memcpy(tmp,buc,sizeof(tmp));
solve(mid+1,r,rt<<1|1);
}
int main(){
rep(i,0,1005)pro[i]=ksm(p,i);
int n;scanf("%d%d",&n,&k);
rep(i,1,n)
{scanf("%d%d",&item[i].fi,&item[i].se);st[i]=1;}
int q;scanf("%d",&q);int item_cnt=n;
rep(i,1,q){
int ty;scanf("%d",&ty);
if(ty==1){
++item_cnt;scanf("%d%d",&item[item_cnt].fi,&item[item_cnt].se);st[item_cnt]=i;
}
else if(ty==2){
int x;scanf("%d",&x);ed[x]=i;
}
else query[i]=1;
}
rep(i,1,item_cnt)if(!ed[i])ed[i]=q;
rep(i,1,item_cnt)
update(1,q,1,st[i],ed[i],i);
solve(1,q,1);
return 0;
}