依旧只有在 UNDER PRESURE 的情况下才能做出来。

考虑 DP，\(dp_i\) 表示杀死第 \(i\) 只怪后最大金币。定义以下函数： \(\operatorname{cost}(h)\) 为力量大于 \(h\) 的长剑的最小金币，可以 \(O(\log n)\) 求。\(\operatorname{pre}(l) = \sum_{i=1}^{l} r_i\)。

转移方程如下：

\[dp_i \gets \operatorname{pre}(i)+\max_{j=max(0,i-k)}^{i-1} {dp_j-\operatorname{pre}(j)-\operatorname{cost}(\max_{t=j+1}^i h_t)} \]

当然条件是：

\[dp_j \ge \operatorname{cost}(\max_{t=j+1}^i h_t) \]

于是线段数优化一下，每个区间维护 \(mx = \max_{j=l}^r{dp_j - \operatorname{pre}(j) - \operatorname{cost}(\max_{t=j+1}^i h_t)}\) 和 \(mn = \min_{j=l}^r{dp_j - \operatorname{cost}(\max_{t=j+1}^i h_t)}\)。

如果一个区间 \(mn\) 小于 \(0\) 则直接删除它（初始化即可），再用单调栈维护点的激活即可。

具体地，当某个怪物到来导致单调栈内某些区间的 \(\operatorname{cost}\) 增加 \(\Delta\) 时，我们对线段树进行区间减去 \(\Delta\)。如果更新后线段树上某节点的 \(mn < 0\)，说明骑士没有足够金币购买对应的长剑，该转移失效。由于 \(mn\) 是单调递减的，一旦某个叶子节点失效，我们直接将其值修改为负无穷，后续不再考虑。每个点最多被移除一次，因此均摊时间复杂度为 \(O(n \log n)\)。

:::info[Code]

#include
#define int long long
using namespace std;
const int N=5e5+5;
const int inf=1e18;
struct node{int mx,mn,tag;node(){mx=-inf,mn=inf,tag=0;return;}
}tr[N<<2];
void push_up(int p){tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);tr[p].mn=min(tr[p<<1].mn,tr[p<<1|1].mn);return;
}
void push_down(int p){if(tr[p].tag){tr[p<<1].mx-=tr[p].tag;tr[p<<1].mn-=tr[p].tag;tr[p<<1].tag+=tr[p].tag;tr[p<<1|1].mx-=tr[p].tag;tr[p<<1|1].mn-=tr[p].tag;tr[p<<1|1].tag+=tr[p].tag;tr[p].tag=0;}return;
}// 移除 mn<0 的失效状态
void del(int p,int l,int r){if(tr[p].mn>=0)	return;if(l==r){tr[p].mx=-inf;tr[p].mn=inf;return;}push_down(p);int mid=l+r>>1;del(p<<1,l,mid);del(p<<1|1,mid+1,r);push_up(p);return;
}
void add(int p,int l,int r,int x,int y,int v){if(ry)	return;if(x<=l&&r<=y){tr[p].mx-=v;tr[p].mn-=v;tr[p].tag+=v;if(tr[p].mn<0)del(p,l,r);return;}push_down(p);int mid=l+r>>1;add(p<<1,l,mid,x,y,v);add(p<<1|1,mid+1,r,x,y,v);push_up(p);return;
}
int qry(int p,int l,int r,int x,int y){if(r>1;int res=-inf;res=max(res,qry(p<<1,l,mid,x,y));res=max(res,qry(p<<1|1,mid+1,r,x,y));return res;
}
void upd(int p,int l,int r,int x,int mx,int mn){if(rx)	return;if(l==r&&l==x){tr[p].mx=mx;tr[p].mn=mn;tr[p].tag=0;return;}push_down(p);int mid=l+r>>1;upd(p<<1,l,mid,x,mx,mn);upd(p<<1|1,mid+1,r,x,mx,mn);push_up(p);return;
}
int n,m,k,x;
int h[N],r[N];
pair b[N];
int pre[N];
int sv[N],suf[N];
int dp[N];
inline int cost(int h){if(!h)	return 0;return suf[lower_bound(sv+1,sv+1+m,h)-sv];
}
stack > st;
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);// freopen("in.in","r",stdin);// freopen("out.out","w",stdout);cin>>n>>m>>k>>x;for(int i=1;i<=n;i++)cin>>h[i]>>r[i];for(int i=1;i<=m;i++)cin>>b[i].first>>b[i].second;sort(b+1,b+1+m);for(int i=1;i<=n;i++)pre[i]=pre[i-1]+r[i];for(int i=1;i<=m;i++)sv[i]=b[i].first;suf[m]=b[m].second;suf[m+1]=inf;for(int i=m-1;i>=1;i--)suf[i]=min(suf[i+1],b[i].second);fill(dp,dp+1+n,-inf);dp[0]=x;upd(1,0,n,0,x,x);for(int i=1;i<=n;i++){st.push(make_tuple(i-1,i-1,0ll));int nw=i-1;while(!st.empty()&&get<2>(st.top())<=h[i]){int L,R,hv;tie(L,R,hv)=st.top();st.pop();int dlt=cost(h[i])-cost(hv);if(dlt>0)add(1,0,n,L,R,dlt);nw=L;}st.push(make_tuple(nw,i-1,h[i]));int res=qry(1,0,n,max(0ll,i-k),i-1);upd(1,0,n,i,res,pre[i]+res);dp[i]=pre[i]+res;}if(dp[n]>-inf/2)	cout<<"Yes";else	cout<<"No";return 0;
}

:::