P5289 [Twelve Provinces Joint Exam 2019] Pipei

The annual variety show “China’s Best Coder” has started again. This season, the show is led by four “dream mentors”: Yazid, Zayid, Little R, and Big R. Each mentor will form their own team and lead contestants to chase their dreams. The four mentors belong to different **factions**. To make the show more interesting, the organizers also divide the mentors into different **camps**, and at the same time impose total team size limits for different camps and different factions: - The four mentors are divided into two **camps**: - Yazid and Little R form the **Blue camp**, and the **sum** of their team sizes must not exceed $C_0$. - Zayid and Big R form the **Red camp**, and the **sum** of their team sizes must not exceed $C_1$. - The four mentors are divided into two **factions**: - Yazid and Zayid belong to the **Duck faction**, and the **sum** of their team sizes must not exceed $D_0$. - Little R and Big R belong to the **R faction**, and the **sum** of their team sizes must not exceed $D_1$.

This season, “China’s Best Coder” invites student elites from all over the country to compete. They come from $n$ different schools in $c$ cities nationwide (cities are numbered from $1$ to $c$, and schools are numbered from $1$ to $n$). The city index of school $i$ is $b_i$, and there are $s_i$ contestants from this school. Besides the total size limits mentioned in **Background**, the mentor selection stage this season has additional rules: - All contestants from the same **city** must join the same **camp**. - All contestants from the same **school** must choose the same **mentor**. For mentors, students from most schools have no **preference**. However, there are $k$ schools where, for each such school, the students have exactly one mentor they dislike. Students in the same school dislike the same mentor, and they **will not join the team of the mentor they dislike**. With so many rules and preferences, as a loyal viewer you want to compute: after all contestants have chosen teams, how many different final outcomes are possible? - Two outcomes are considered different if and only if there exists a school such that, in the two outcomes, contestants from this school join teams led by different mentors. - Since the answer may be large, output it modulo $998244353$.

Each test file contains multiple test cases. The first line contains a non-negative integer $T$ indicating the number of test cases. Then each test case is described as follows: - Line $1$: two positive integers $n$, $c$, representing the number of schools and the number of cities. - Line $2$: four positive integers $C_0$, $C_1$, $D_0$, $D_1$, representing the four limits described in the statement. - Next $n$ lines, each with two positive integers: - On line $i$ of this part, the two numbers are $b_i$, $s_i$, representing the city of school $i$ and its number of contestants. - It is guaranteed that $b_i \leqslant c$, $s_i \leqslant\min\left\{M, 10\right\}$. Here $M = \max \left\{C_0, C_1, D_0, D_1\right\}$. - Next line: a non-negative integer $k$, the number of schools with preferences. - Next $k$ lines, each with two integers $i$, $p$, describing that contestants from school $i$ have a preference: - Here $p$ is an integer from $0$ to $3$, describing the mentor disliked by this school: $0$ means Yazid, $1$ means Little R, $2$ means Zayid, $3$ means Big R. - It is guaranteed that $1 \leqslant i \leqslant n$, and all $i$ are distinct. For each input line, if it contains multiple numbers, they are separated by a single space.

Output the answer for each test case in order: - For each test case, output one line with one integer, the number of possible outcomes modulo $998244353$.

### Sample 1 Explanation For the $1$st test case: - The only city $1$ contains a total of $3$ contestants, but the total size limit of the Red camp is $2$, so it cannot hold these contestants. Therefore, they are forced to choose the Blue camp. - Based on this, since contestants from school $1$ dislike mentor Yazid, they must join mentor Little R in the R faction. - Because the total size limit of the R faction is $2$, mentor Little R’s team cannot hold the contestants from school $2$, so they are forced to join mentor Yazid’s team. - Therefore, there is only one possible outcome. For the $2$nd test case: - An obvious fact is that all contestants in city $1$ cannot join the Blue camp, because the total number of contestants in city $1$ exceeds the total size limit of the Blue camp, so they are forced to all join the Red camp. - If contestants from city $2$ join the Blue camp, a small calculation shows there are $15$ possible outcomes. - If contestants from city $2$ join the Red camp, a small calculation shows there are $7$ possible outcomes. - Therefore, the number of possible outcomes is $15 + 7 = 22$. ### Constraints and Notes ::cute-table{tuack} | Test point | $n$ | $c$ | $k$ | $m$ | | :-: | :-: | :-: | :-: | :-: | | $1$ | $=1$ | $=n$ | $\le1$ | $=1$ | | $2$ | $=10$ | ^ | $\le10$ | $\le100$ | | $3$ | $=20$ | ^ | $=0$ | ^ | | $4$ | $=30$ | ^ | ^ | ^ | | $5$ | ^ | ^ | $\le30$ | $\le500$ | | $6$ | $=500$ | ^ | $=0$ | $\le1000$ | | $7$ | ^ | $=30$ | $=30$ | ^ | | $8$ | ^ | $=n$ | ^ | ^ | | $9$ | $=1000$ | ^ | $=0$ | $\le2500$ | | $10$ | ^ | ^ | $= 30$ | ^ | Here, $M = \max\left\{C_0, C_1, D_0, D_1\right\}$. For all test points, it is guaranteed that $T \leqslant5$. For each test case in all test points, it is guaranteed that $c \leqslant n \leqslant 1000$, $k \leqslant 30$, $M \leqslant 2500$, $1 \leqslant s_i \leqslant \min\left\{M, 10\right\}$. **Also, note that the testdata does not guarantee that all $c$ cities have participating schools.** ### Additional Hint There are also two additional sample files. Please download them from the attachments. A warm reminder from the Twelve Provinces Joint Exam problem committee: **There are thousands of testdata, clearing arrays is the first rule.** **If you forget to clear in multiple tests, you will cry with a zero score.** Translated by ChatGPT 5