Taco Fair Organization Problem

You are tasked with organizing a fair under strict constraints. There are (N) students and (P) projects (with (1 \le P \le N)). Each student is eligible to participate in a subset of these projects. Each project (j) is characterized by a required budget (c_j), a minimum number of students (l_j) and a maximum number of students (r_j) allowed to participate. In order to run the fair, you must select exactly (P) students (one selection per project slot) such that for every project (j), the total number of chosen students who are eligible for it is between (l_j) and (r_j) (inclusive), and the sum of all projects' budgets does not exceed the total available budget (B).

Formally, given:

[ \begin{aligned} N,& \text{ the number of students},\ P,& \text{ the number of projects},\ B,& \text{ the total available budget},\ {S_i}{i=1}^{N},& \text{ where each } S_i \subseteq {1,2,\ldots,P} \text{ denotes the projects student } i \text{ can participate in},\ {(c_j, l_j, r_j)}{j=1}^{P},& \text{ representing the cost and the minimum and maximum number of students required for project } j. \end{aligned} ]

Your task is to determine whether there exists a selection of exactly (P) students (by choosing a subset of indices of size (P) from ({1,2,\ldots,N})) such that for every project (j):

[ l_j \leq \text{number of chosen students with } j \in S_i \leq r_j\quad \text{and} \quad \sum_{j=1}^{P} c_j \leq B. ]

Output “YES” if such a selection exists; otherwise, output “NO". Note that the input size is small and a brute force approach over all (\binom{N}{P}) combinations is acceptable.

inputFormat

Input is given from standard input (stdin). The first line contains a single integer (T), the number of test cases. For each test case:

• The first line contains three integers: (N) (number of students), (P) (number of projects), and (B) (total available budget).
• The next (N) lines each contain space‐separated integers, representing the list of projects that the corresponding student can participate in.
• The following (P) lines each contain three integers: the required budget, the minimum number of students, and the maximum number of students for each project.

outputFormat

For each test case, print a single line (stdout) containing “YES” if it is possible to organize the fair according to the given constraints, or “NO” otherwise.## sample

1
3 2 1000
1
1 2
2
500 1 2
300 1 3

YES