P2823 Timetable

Xiao A is a supervisor at a call service center, and his team has a large number of people. Everyone on the team spends their time attending meetings and talking to customers over the phone, and of course working on the team's research projects also takes up their time.

Each person can only choose one of attending meetings, talking to customers, or working on research projects in any given hour. To improve efficiency, each hour must be devoted entirely to one of these tasks, and they cannot switch in the middle. Xiao A lives in a strange place where a week has $D$ days, labeled from $1$ to $D$. To protect the employees' voices, person $i$ can talk to customers for at most $L_i$ hours per week. Meetings are pre-planned, and the times at which each person needs to attend meetings are fixed. The call service center can respond to customer calls for $H$ hours each day; for convenience, these $H$ hours are labeled from $1$ to $H$. For each day and hour of the week, the number of customers connecting to the call service center is known. Therefore, Xiao A knows that on day $i$ at hour $j$, exactly $R_{i,j}$ employees must be scheduled to talk to customers. If person $k$ has no meeting at day $i$, hour $j$ and can take customer calls, then $F_{k,i,j}=1$; otherwise $F_{k,i,j}=0$. Again, Xiao A's world is quite strange: not only might a week not have $7$ days, but a day might also not have $24$ hours. Xiao A needs to create a timetable for each employee. Since employees also need to eat and rest, there is a lunch break every day from $L_{\text{T}_\text{begin}}$ to $L_{\text{T}_\text{end}}$ inclusive. Xiao A must ensure that each employee has at least one hour within this interval during which they are neither in a meeting nor talking to customers, so that they can eat, rest, or do what they want. If someone has neither a meeting nor customer calls in an hour, they can work on the company’s research projects during that hour, and this counts as working time. They might also work on their own projects, but that does not count as working time. Xiao A wants to know whether it is possible to arrange such a timetable that satisfies all of the following: - Each person spends at most $N$ hours per day on meetings and customer calls. - Each person spends at most $L_i$ hours per week talking to customers. - Each person has at least one hour during the lunch break when they are neither in a meeting nor talking to customers. - For day $i$, hour $j$, exactly $R_{i,j}$ people are talking to customers.

The first line contains a positive integer $T$, the number of testdata sets. For each testdata set, the first line contains four integers $P, D, H, N$, representing the number of people in the team, the number of working days per week, the number of hours per day during which the call service center can respond to customer calls, and the daily per-person limit on time spent on meetings and customer calls, respectively. The next line contains $P$ integers, where the $i$-th integer is $L_i$. The next line contains two integers $L_{\text{T}_\text{begin}}$ and $L_{\text{T}_\text{end}}$, representing the lunch break interval. Then follow $D$ lines, each containing $H$ integers; on the $i$-th line, the $j$-th integer is $R_{i,j}$. Then follow $P$ blocks; each block has $D$ lines, and each line contains $H$ integers. In the $k$-th block, the number on the $i$-th line and $j$-th position is $F_{k,i,j}$.

Output $T$ lines. For the $i$-th testdata set, print `Yes` if a feasible schedule exists; otherwise, print `No`.

Constraints: For $100\%$ of the testdata, the following hold: $1 \leq T \leq 5, 1 \leq N \leq H \leq 70$. $1 \leq D, P \leq 70, 1 \leq L_i \leq N \times D, 0 \leq R_{i,j} \leq 15$. $0 \leq F_{k,i,j} \leq 1, 1 \leq L_{\text{T}_\text{begin}} \leq L_{\text{T}_\text{end}} \leq H$. Translated by ChatGPT 5