Description

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.

Input Format

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 Format

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

2
2 2 3 2
4 1
2 3
0 1 1
0 1 0
1 1 1
1 1 1
1 1 1
1 0 1
2 2 3 2
4 1
2 3
0 1 2
0 1 0
1 1 1
1 1 1
1 1 1
1 0 1

Yes
No

Hint

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