注意

問題文中の数式が正しく表示されない場合は、新システム上のページにアクセスし直してご覧ください。

問題文

この問題は「問題 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$ つ存在する