分析：该题有2个地方要注意：所有的车要么不坐要么就坐满，这个贪心策略很容易证明是正确的，还有一点就是最后一辆车除外。
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std; const int MaX = ;
int N, K, D, S;
struct Node {
int ti;
int qz;
}seq[MaX];
int dp[MaX][MaX];
// dp[i][j]表示第i台车来的时候，等候人数为j时的最少开销 void solve() {
memset(dp, 0xff, sizeof (dp));
dp[][N] = ; // 初始化
for (int i = ; i <= K; ++i) {
const int &ti = seq[i].ti;
const int &qz = seq[i].qz;
for (int j = ; j <= N; ++j) {
if (dp[i-][j] != -) dp[i][j] = dp[i-][j] + j*(ti-seq[i-].ti); // 不乘坐
if (j == ) { // 最后一辆车可能不能坐满
for (int k = ; k <= qz; ++k) {
if (k <= N && dp[i-][k] != -) {
if (dp[i][] == -) {
dp[i][] = D + dp[i-][k] + k*(ti-seq[i-].ti);
} else {
dp[i][] = min(dp[i][], D + dp[i-][k] + k*(ti-seq[i-].ti));
}
}
}
} else {
if ((j+qz) <= N && dp[i-][j+qz] != -) {
if (dp[i][j] == -) {
dp[i][j] = D + dp[i-][j+qz] + (j+qz)*(ti-seq[i-].ti);
} else {
dp[i][j] = min(dp[i][j], D + dp[i-][j+qz] + (j+qz)*(ti-seq[i-].ti));
}
}
}
}
}
printf("%d\n", dp[K][]);
} int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d %d %d %d", &N, &K, &D, &S);
int sum = ;
for (int i = ; i <= K; ++i) {
scanf("%d %d", &seq[i].ti, &seq[i].qz);
sum += seq[i].qz;
}
if (sum < N) {
puts("impossible");
continue;
}
solve();
}
return ;
}