#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn =
1e4+
10;
const int INF =
0x3f3f3f3f;
int dp[maxn], n, m, k;
int cal(
int x,
int y){
int num = x/k +
1;
if(x+y <= num*k)
return x+y;
else return num*k+y;
}
int main(){
int T;
scanf(
"%d", &T);
while(T--){
scanf(
"%d%d%d", &n, &m, &k);
memset(dp, INF,
sizeof(dp));
dp[
0] =
0;
int a,b;
while(n--){
scanf(
"%d%d", &a, &b);
a++;
for(
int i =
1e4; i >= b; i--)
if(dp[i-b] != INF) dp[i] = min(dp[i], cal(dp[i-b], a));
}
int ans =
1e4;
while(dp[ans] > k*m) ans--;
printf(
"%d\n", ans);
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-1123455.html