0 Judge
Code: 0
因為上次出任務賺了不少金,達克妮絲想要組一個新的套裝;由於某些原因,她想要這個套裝的防禦力越低越好。一個套裝的防禦力取決於他是由幾個配件組合而成,比方說三個配件組成的套裝防禦力 $= 3$。
但是基於十字騎士工會的規定,為了騎士自身安全和騎士的職業名譽,一個騎士出任務時必須妥善地蓋住身上每個指定部位。所以達克妮絲請求你的幫助:以現有的配件,請問有幾種套裝組合能滿足達克妮絲和工會的要求?
每筆測資會有 $N + 1$ 行,第一行包含兩個整數 $N$ $K$ ,分別代表:
$N$:可挑選的配件有幾種
$K$:身上有多少部位需要覆蓋
接著有 $N$ 行,分別表示一個配件。在其中的第 $i$ 行,會先有一個整數 $P_i$ ,表示這個配件可以覆蓋到不同的身體部位數;接著會有 $P_i$ 個不同的整數 ( 範圍: $1$ ~ $K$ ) 分別代表這些身體部位。
$ 1 \leq N \leq 5000 $
$ 1 \leq K \leq 10 $
對任意 $i$: $ 1 \leq P_i \leq K $
如果現有的配件湊不出符合工會要求的套裝,輸出 -1 並結束即可。否則輸出兩個整數 $L$ $C$ ,分別代表:
$L$:想拼出一個符合工會要求的套裝,最低的防禦力可以是多少
$C$:有多少種同時滿足 (1) 防禦力 $ = L$ (2) 覆蓋全身 兩項要求的組合
由於 $C$ 可能數字龐大,請先 mod 1000000007 後輸出。
4 3
1 1
1 2
1 3
2 2 3
2 1
4 5
3 1 2 3
3 2 3 4
3 3 4 5
2 1 5
2 2
3 4
2 1 2
2 2 3
1 1
-1
在第一筆範例測資,我們可以用第一和第四個配件湊出一個防禦力 $= 2$ 的套裝;顯然沒有其他能湊出同樣防禦力的合法套裝,也不可能湊出防禦力更低的合法套裝。
Test case #1~2 : $N \leq 20$ ( score: 20 )
Test case #3~5 : $N \leq 5000$ ( score: 80 )