Minimum Time Software Patching

T Company has developed a software with \(n\) bugs and has provided \(m\) patches. Each patch \(i\) is associated with four sets: \(B1_i, B2_i, F1_i, F2_i\) and a time cost. A patch can only be applied if the current software bug set contains all bugs in \(B1_i\) and none of the bugs in \(B2_i\). When applied, patch \(i\) removes all bugs in \(F1_i\) and adds the bugs in \(F2_i\). The goal is to apply a sequence of patches such that the final software contains no bugs, while the total patching time is minimized. If such a sequence does not exist, output -1.

Input Format:

• The first line contains two integers \(n\) and \(m\), representing the number of bugs and the number of patches.
• For each patch \(i\) (from 1 to \(m\)), the next five lines are provided in order:
  1. An integer denoting the time cost of the patch.
  2. A line starting with an integer \(k_{B1}\) (the number of bugs in \(B1_i\)) followed by \(k_{B1}\) distinct integers representing the bugs in \(B1_i\).
  3. A line starting with an integer \(k_{B2}\) (the number of bugs in \(B2_i\)) followed by \(k_{B2}\) distinct integers representing the bugs in \(B2_i\). If there is no bug, the line will contain only 0.
  4. A line starting with an integer \(k_{F1}\) (the number of bugs in \(F1_i\)) followed by \(k_{F1}\) distinct integers representing the bugs in \(F1_i\).
  5. A line starting with an integer \(k_{F2}\) (the number of bugs in \(F2_i\)) followed by \(k_{F2}\) distinct integers representing the bugs in \(F2_i\). If there is no bug, the line will contain only 0.

The software initially contains all \(n\) bugs (bugs are numbered from 1 to \(n\)).

Output Format:

• Output a single integer: the minimum total time required to obtain a bug-free software, or \(-1\) if it is impossible.

inputFormat

The input begins with two integers \(n\) and \(m\). Following that, for each patch, there are 5 lines as described in the problem statement. Each line for a patch is formatted as follows:

• Line 1: An integer representing the time cost of the patch.
• Line 2: An integer \(k_{B1}\) followed by \(k_{B1}\) bug numbers.
• Line 3: An integer \(k_{B2}\) followed by \(k_{B2}\) bug numbers (or just 0 if empty).
• Line 4: An integer \(k_{F1}\) followed by \(k_{F1}\) bug numbers.
• Line 5: An integer \(k_{F2}\) followed by \(k_{F2}\) bug numbers (or just 0 if empty).

outputFormat

Output a single integer which is the minimum total time to completely fix the software (i.e. to remove all bugs). If it is impossible to remove all bugs with the available patches, output \(-1\).

sample

2 1
3
2 1 2
0
2 1 2
0

3