64. 達克妮絲的裝備

0 Judge

Code: 0


Problem Description

因為上次出任務賺了不少金,達克妮絲想要組一個新的套裝;由於某些原因,她想要這個套裝的防禦力越低越好。一個套裝的防禦力取決於他是由幾個配件組合而成,比方說三個配件組成的套裝防禦力 $= 3$。

但是基於十字騎士工會的規定,為了騎士自身安全和騎士的職業名譽,一個騎士出任務時必須妥善地蓋住身上每個指定部位。所以達克妮絲請求你的幫助:以現有的配件,請問有幾種套裝組合能滿足達克妮絲和工會的要求?

Input Format

每筆測資會有 $N + 1$ 行,第一行包含兩個整數 $N$ $K$ ,分別代表:

$N$:可挑選的配件有幾種

$K$:身上有多少部位需要覆蓋

接著有 $N$ 行,分別表示一個配件。在其中的第 $i$ 行,會先有一個整數 $P_i$ ,表示這個配件可以覆蓋到不同的身體部位數;接著會有 $P_i$ 個不同的整數 ( 範圍: $1$ ~ $K$ ) 分別代表這些身體部位。

Input Constraints

$ 1 \leq N \leq 5000 $

$ 1 \leq K \leq 10 $

對任意 $i$: $ 1 \leq P_i \leq K $

Output Format

如果現有的配件湊不出符合工會要求的套裝,輸出 -1 並結束即可。否則輸出兩個整數 $L$ $C$ ,分別代表:

$L$:想拼出一個符合工會要求的套裝,最低的防禦力可以是多少

$C$:有多少種同時滿足 (1) 防禦力 $ = L$ (2) 覆蓋全身 兩項要求的組合

由於 $C$ 可能數字龐大,請先 mod 1000000007 後輸出。

Sample IO

Sample In 1

4 3
1 1
1 2
1 3
2 2 3

Sample Out 1

2 1

Sample In 2

4 5
3 1 2 3
3 2 3 4
3 3 4 5
2 1 5

Sample Out 2

2 2

Sample In 3

3 4
2 1 2
2 2 3
1 1

Sample Out 3

-1

Sample Explanation

在第一筆範例測資,我們可以用第一和第四個配件湊出一個防禦力 $= 2$ 的套裝;顯然沒有其他能湊出同樣防禦力的合法套裝,也不可能湊出防禦力更低的合法套裝。

Score Distribution

Test case #1~2 : $N \leq 20$ ( score: 20 )

Test case #3~5 : $N \leq 5000$ ( score: 80 )


Judge Setting

run-time limit: 10000 ms
memory limit: 256000000 byte
測資數量: 5