已知有 $n$ 個寶盒編號 $0$ 到 $n-1$ 以及 $m$ 種鑰匙編號 $0$ 到 $m-1$。一開始你有 $t$ 種鑰匙分別為 $x_1, \cdots, x_t$。
每一個寶盒要打開都需要同時擁有 $k$ 種鑰匙,第 $i$ 個寶盒分別需要 $r_{i1}, r_{i2}, \cdots, r_{ik}$ 種類的鑰匙。每個寶盒打開後都會得到 $k$ 種鑰匙,第 $i$ 個寶盒打開後分別會得到 $s_{i1}, s_{i2}, \cdots, s_{ik}$ 種類的鑰匙,當拿到新的鑰匙之後可以繼續開啟新的寶盒。保證寶盒內的鑰匙不會重複,並且每種鑰匙可以開啟的寶盒數量不超過 $60$。
請輸出最多可以開啟多少個寶盒。
子問題一 (20%) $k=1$, $1 \le n, m \le 100$
子問題二 (20%) $k=1$, $1 \le n, m \le 10^5$
子問題三 (60%) $1 \le k \le 5$, $1 \le n, m \le 10^5$
第一行輸入三個正整數 $n, m, k (1 \le n, m \le 10^5, 1 \le k \le 5)$ 代表有 $n$ 個寶盒,$m$ 種鑰匙以及每個寶盒需要的鑰匙數量 $k$。
接下來輸入一行,第一個數字 $t$ 代表一開始有的鑰匙種類數量,後面有 $t$ 個數字代表這些鑰匙分別的種類。
接下來有 $n$ 行,每一行有 $k$ 個數字,代表要開啟第 $i$ 個寶盒的第 $j$ 種鑰匙為 $r_{ij}$。
最後有 $n$ 行,每一行有 $k$ 個數字,代表開啟第 $i$ 個寶盒後得到的第 $j$ 種鑰匙為 $s_{ij}$。
輸出一個正整數,代表可以開啟的寶盒數量。
5 5 1 2 0 1 0 2 4 3 1 1 2 4 3 3
3
10 8 2 3 6 5 2 5 6 2 7 2 0 4 5 5 1 3 0 4 2 2 4 5 3 5 6 5 0 0 6 1 7 3 2 2 1 7 3 4 7 4 5 4 1 7 5
5
ID | User | Problem | Subject | Hit | Post Date |
41022 | glps1004@gma ... (Ian) | k734 | 158 | 2024-06-25 15:55 | |
41021 | glps1004@gma ... (Ian) | k734 | 72 | 2024-06-25 15:51 | |
38026 | aoscar0717@g ... (吳赤赤宥) | k734 | 477 | 2023-10-22 22:07 | |
37778 | edoctopus322 ... (Moon Jam) | k734 | 669 | 2023-10-07 01:14 | |
37243 | frankleeplay ... (LJH-code) | k734 | 474 | 2023-08-27 16:15 |