C - Problem Setting C /

Time Limit: 30 sec / Memory Limit: 1024 MB

### 問題文

この問題は「問題 A」と同一の問題であるが、制約が異なる。問題文本文は問題 A のページを、制約は以下を参照のこと。

### 入力

• 3 \leq N \leq 10
• 1 \leq K \leq 2^N
• 0 \leq d_i \leq 6
• 1 \leq \left|c_i \right| \leq 100
• 1 \leq v_{i, j} \leq N
• 全ての j (1 \leq j \lt d_i) について、v_{i, j} < v_{i, j+1}
• i \neq j ならば \left[ v_{i, 1}, \dots , v_{i, d_i} \right] \neq \left[ v_{j, 1}, \dots, v_{j, d_j} \right]
• d_i = 0 となる行は高々 1 度しか登場しない
• 全ての k (1 \leq k \leq N) に対して、k = v_{i, j} を満たす (i, j) が少なくとも 1 つ存在する

In case equations are not displayed properly, we recommend taking a look at the new AtCoder system.

### Problem Setting

The task in problem setting C is almost equivalent to problem setting A. Hence, for details on the task the contestant is refered to problem setting A. The only difference in Problem C is the shape of the higher order pseudo-Boolean function which serves as an input. This input will now have degree at most 6 (d=6), while coefficients are provided for all possible terms of the function. For details of the input problem contestants are referred to the section below.

### Input Format

The following requirements shall be imposed on the input problem.

• 3 \leq N \leq 10
• 1 \leq K \leq 2^N
• 0 \leq d_i \leq 6
• 1 \leq \left|c_i \right| \leq 100
• 1 \leq v_{i, j} \leq N
• For all j (1 \leq j \lt d_i) we require v_{i, j} < v_{i, j+1}
• For two lines i,j with i \neq j we require \left[ v_{i, 1}, \dots , v_{i, d_i} \right] \neq \left[ v_{j, 1}, \dots, v_{j, d_j} \right], i.e., two separate lines shall not encode the same type of monomial.
• The line d_i = 0 should not exceed beyond the coefficient.
• All of the variables k (1 \leq k \leq N) should appear in at least one of the term, i.e., there exists at least one v_{i,j} such that k = v_{i, j}.