Hi, I just came up with a problem and I honestly don't know how to approach it. Can somebody help me? The problem is as followed:

Jack recently discovered a new online game. After completing the newbie questline, he's allowed to choose $$$N$$$ gift boxes out of $$$M$$$ available ones. Each gift box grants one point to each attribute listed on it. The game has $$$P$$$ different attributes.

Although Jack could simply pick any boxes, experienced players advise that keeping attributes balanced is crucial for long-term success. Therefore, Jack wants to choose $$$N$$$ gift boxes such that the resulting distribution of attribute points is as balanced as possible.

For each of the P attributes, there is a recommended balanced range $$$[L_i, R_i]$$$, meaning Jack should aim to have between $$$L_i$$$ and $$$R_i$$$ points in attribute $$$i$$$ (inclusive) after choosing his boxes. An attribute is considered balanced if the number of points Jack has in that attribute lies within the corresponding interval.

Your task is to help Jack choose $$$N$$$ gift boxes such that the number of balanced attributes is maximized. If there are multiple selections that lead to the same maximum number of balanced attributes, you may output any of them.

$$$\large{\textbf{Input}}$$$

The first line contains three integers $$$N, M, P$$$ $$$(1 \le N \le 10, 1 \le M \le 60, 1 \le P \le 20)$$$ — the number of gift boxes Jack must choose, the total number of gift boxes available, and the number of distinct attributes in the game.

The next $$$P$$$ lines each contain two integers $$$L_i$$$ and $$$R_i$$$ $$$(1 \le L_i \le R_i \le 4)$$$ — the recommended balanced interval for the $$$i$$$-th attribute.

Each of the following $$$M$$$ lines describes a gift box. Each line begins with an integer $$$X$$$ $$$(1 \le X \le 3)$$$, followed by $$$X$$$ distinct integers between $$$1$$$ and $$$P$$$, representing the attributes to which this gift box contributes $$$1$$$ point.

$$$\large{\textbf{Output}}$$$

On the first line, print a single integer $$$S$$$ — the maximum number of attributes that can be balanced by choosing $$$N$$$ gift boxes.

On the second line, print $$$N$$$ space-separated integers — the indices ($$$1$$$-based) of the gift boxes selected (in any order) that achieve the maximum balance score.

$$$\large{\textbf{Example}}$$$

$$$\textbf{Input}$$$

4 6 8

2 2

2 3

2 3

2 3

2 3

2 3

2 2

3 4

2 1 5

2 1 5

2 2 4

2 2 4

3 3 6 7

2 3 8

$$$\textbf{Output}$$$

4

1 2 3 4

$$$\large{\textbf{Note}}$$$

You can choose $$$4$$$ gift boxes with indices $$$1, 2, 3, 4$$$ with $$$4$$$ different attributes which are $$$1, 5, 2, 4$$$.

Thanks in advance.