#include <bits/stdc++.h>
namespace // my guiding star
{
#define filein(x) freopen(x".in", "r", stdin);
#define fileout(x) freopen(x, "w", stdout);
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);
#define files(x) freopen(x".in", "r", stdin), freopen(x".ans", "w", stdout);
using namespace std;
#define cT const T&
template<typename T>
inline T chkmin(T& x, cT y){if (x > y) x = y; return x;}
template<typename T>
inline T chkmax(T& x, cT y){if (x < y) x = y; return x;}
template <typename T>
inline bool inrange(cT x, cT l, cT r){return (l <= x) && (x <= r);}
template <typename T>
inline bool inrange(cT l, cT r, cT L, cT R){return (L <= l) && (r <= R);}
#undef cT
typedef long long ll;
typedef unsigned long long u64;
typedef double db;
typedef long double ldb;
typedef unsigned u32;
template <typename T>
using pr = pair<T, T>;
typedef pr<int> pii;
typedef pr<ll> pll;
typedef pr<db> pdd;
typedef complex<double> cp;
typedef vector<int> vi;
inline void YN(bool x){puts((x) ? "Yes" : "No");}
}
const int N = 5e5 + 233;
int n, m, a[N], b[N], c[N];
ll dp[N];
int main()
{
	int T; scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d", &n, &m);
		if (n > 5000) break;
		for (int i=1; i<=n; i++) scanf("%d%d", a+i, b+i);
		for (int i=1; i<=n; i++) c[i] = a[i] - (b[i] < 0);
		ll ans = 0;
		for (int i=1; i<=n; i++)
		{
			ll bias = 0; dp[i] = -INF;
			for (int j=i-1; j>=0; j--)
			{
				if (c[i] >= a[j + 1]) bias += b[j + 1];
				chkmax(dp[i], dp[j] - 1ll * m * max(c[i] - c[j], 0) + bias);
			}
			chkmax(ans, dp[i]);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:48:47: error: ‘INF’ was not declared in this scope
   48 |                         ll bias = 0; dp[i] = -INF;
      |                                               ^~~
answer.code:38:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |         int T; scanf("%d", &T);
      |                ~~~~~^~~~~~~~~~
answer.code:41:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   41 |                 scanf("%d%d", &n, &m);
      |                 ~~~~~^~~~~~~~~~~~~~~~
answer.code:43:47: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |                 for (int i=1; i<=n; i++) scanf("%d%d", a+i, b+i);
      |                                          ~~~~~^~~~~~~~~~~~~~~~~~