1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
| #include <bits/stdc++.h>
inline int rd() { int a = 1, b = 0; char c = getchar(); while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar(); while (isdigit(c)) b = b * 10 + c - '0', c = getchar(); return a ? b : -b; }
const int N = 2505, P = 998244353;
inline void check(int &x) { x -= P, x += x < 0 ? P : 0; }
int n, c, C0, C1, D0, D1, b[N], s[N], K, hate[N]; int city_s[N], sum_s, city_hate[N]; int f[N], g[N], h[N][N], t1[N][N], t2[N][N]; int ans, ss, sc;
inline int calc_f(int x) { int l = std::max(0, sum_s - x - C1), r = C0 - x, ret = 0; if (l <= r) { ret = f[r]; if (l != 0) check(ret += P - f[l - 1]); } return ret; }
inline int calc_g(int x) { int l = std::max(0, sum_s - x - D1), r = D0 - x, ret = 0; if (l <= r) { ret = g[r]; if (l != 0) check(ret += P - g[l - 1]); } return ret; }
inline void solve() {
memset(b, 0, sizeof(b)); memset(s, 0, sizeof(s)); memset(hate, -1, sizeof(hate)); memset(city_s, 0, sizeof(city_s)); memset(city_hate, 0, sizeof(city_hate)); sum_s = 0; memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g)); memset(h, 0, sizeof(h)); memset(t1, 0, sizeof(t1)); memset(t2, 0, sizeof(t2)); ans = 0; ss = sc = 0;
n = rd(), c = rd(), C0 = rd(), C1 = rd(), D0 = rd(), D1 = rd(); for (int i = 1; i <= n; ++i) { b[i] = rd(), s[i] = rd(); city_s[b[i]] += s[i]; sum_s += s[i]; } K = rd(); for (int i = 1; i <= K; ++i) { int x = rd(), p = rd(); hate[x] = p; city_hate[b[x]] = 1; }
f[0] = 1; for (int i = 1; i <= c; ++i) { if (city_hate[i] !city_s[i]) continue; for (int j = C0; j >= city_s[i]; --j) check(f[j] += f[j - city_s[i]]); }
g[0] = 1; for (int i = 1; i <= n; ++i) { if (hate[i] != -1 !s[i]) continue; for (int j = D0; j >= s[i]; --j) check(g[j] += g[j - s[i]]); }
h[0][0] = 1;
for (int city = 1; city <= c; ++city) { if (!city_hate[city]) continue;
sc = std::min(sc + city_s[city], C0);
for (int i = 0; i <= sc; ++i) for (int j = 0; j <= ss; ++j) t1[i][j] = t2[i][j] = h[i][j];
for (int school = 1; school <= n; ++school) { if (b[school] != city hate[school] == -1) continue; ss = std::min(ss + s[school], D0); for (int i = sc; ~i; --i) { for (int j = ss; ~j; --j) { check(t1[i][j] = (j >= s[school] ? t1[i][j - s[school]] * (hate[school] != 0): 0) + t1[i][j] * (hate[school] != 1)); check(t2[i][j] = (j >= s[school] ? t2[i][j - s[school]] * (hate[school] != 2): 0) + t2[i][j] * (hate[school] != 3)); } } }
for (int i = 0; i <= sc; ++i) { for (int j = 0; j <= ss; ++j) { check(h[i][j] = (i >= city_s[city] ? t1[i - city_s[city]][j] : 0) + t2[i][j]); } }
}
for (int i = 1; i <= C0; ++i) check(f[i] += f[i - 1]); for (int i = 1; i <= D0; ++i) check(g[i] += g[i - 1]);
for (int i = 0; i <= sc; ++i) { for (int j = 0; j <= ss; ++j) { check(ans += 1ll * h[i][j] * calc_f(i) % P * calc_g(j) % P); } }
std::cout << ans << std::endl;
}
int main() { int T = rd(); while (T--) solve(); return 0; }
|