样例也没过，悲

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 2;
int id,T,n,k,t,p;
int a[N][2],sum[N][2];
int dp[N][2][2];
void work()
{
	int ans = -1e18;
	cin >> n >> k >> t >> p;
	memset(dp , -0x3f , sizeof dp);
	for(int i = 1;i <= n;i ++)
	{
		cin >> a[i][0] >> a[i][1];
		sum[i][0] = sum[i - 1][0] + a[i][0];
		sum[i][1] = sum[i - 1][1] + a[i][1];
	}
	for(int i = 1;i <= n;i ++)
	{
		dp[i][0][0] = sum[i][0];
		dp[i][0][1] = sum[i][1];
	}
	ans = max(dp[n][0][1] , dp[n][0][0]);
	for(int i = 1;i <= n;i ++)
	{
		dp[i][1][0] = sum[i - 1][1] + sum[n][0] - sum[i - 1][0];
		dp[i][1][1] = sum[i - 1][0] + sum[n][1] - sum[i - 1][1];
	}
	ans = max(ans , max(dp[n][1][0] , dp[n][1][1]));
	for(int j = 2;j <= k;j ++)
	{
		int Max0 ,Max1;
		Max0 = Max1 = -0x3f3f3f3f3f3f3f3f;
		deque<int> que0,que1;
		for(int i = j;i <= n;i ++)
		{
			dp[i][j & 1][0] = dp[i][j & 1][1] = -0x3f3f3f3f3f3f3f3f;
		}
		que0.push_back(j - 1);
		que1.push_back(j - 1);
		for(int i = j;i <= n;i ++)
		{
			while(que0.size() && que0.front() < i - t) que0.pop_front();
			while(que1.size() && que1.front() < i - t) que1.pop_front();
			if(que1.size())
			{
				dp[i][j & 1][0] = max(max(dp[i][j & 1][0] , Max1 + a[i][0] + sum[i - 1][1]), dp[que1.front()][(j - 1) & 1][1] + p + a[i][0] + sum[i - 1][1] - sum[que1.front()][1]);
			}
			else
			{
				dp[i][j & 1][0] = max(dp[i][j & 1][0] , Max1 + a[i][0] + sum[i - 1][1]);
			}
			if(que0.size())
			{
				dp[i][j & 1][1] = max(max(dp[i][j & 1][1] , Max0 + a[i][1] + sum[i - 1][0]), dp[que0.front()][(j - 1) & 1][0] + p + a[i][1] + sum[i - 1][0] - sum[que0.front()][0]);
			}
			else
			{
				dp[i][j & 1][1] = max(dp[i][j & 1][1] , Max0 + a[i][1] + sum[i - 1][0]);
			}
			ans = max(ans , max(dp[i][j & 1][0] + sum[n][0] - sum[i][0] , dp[i][j & 1][1] + sum[n][1] - sum[i][1]));
			while(que0.size() && dp[que0.back()][(j - 1) & 1][0] - sum[que0.back()][0] < dp[i][(j - 1) & 1][0] - sum[i][0]) que0.pop_back();
			while(que1.size() && dp[que1.back()][(j - 1) & 1][1] - sum[que1.back()][1] < dp[i][(j - 1) & 1][1] - sum[i][1]) que1.pop_back();
			que0.push_back(i);que1.push_back(i);
			if(i > t && i - t > j)
			{
				Max0 = max(Max0 , dp[i - t][(j - 1) & 1][0] - sum[i - t][0]);
				Max1 = max(Max1 , dp[i - t][(j - 1) & 1][1] - sum[i - t][1]);
			}
		}
	}
	cout << ans << "\n";
	return ;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin >> id >> T;
	while(T --)
	{
		work();
	} 
	
	return 0;
}