AT_abc404_d [ABC404D] Goin' to the Zoo

In the country of AtCoder there are $ N $ zoos, numbered $ 1 $ to $ N $ . The admission fee for zoo $ i $ is $ C_i $ yen. Mr. Suzuki likes $ M $ kinds of animals, animals $ 1,\dots,M $ . Animal $ i $ can be seen at $ K_i $ zoos, namely zoos $ A_{i,1},\dots,A_{i,K_i} $ . Find the minimum total admission fee required to see all $ M $ kinds of animals at least twice each. If you visit the same zoo multiple times, the animals there are considered seen once per every visit.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ C_1 $ $ \dots $ $ C_N $ $ K_1 $ $ A_{1,1} $ $ \dots $ $ A_{1,K_1} $ $ \vdots $ $ K_M $ $ A_{M,1} $ $ \dots $ $ A_{M,K_M} $

Output the minimum total admission fee.

### Sample Explanation 1 For example, the following schedule achieves seeing animals $ 1,2,3 $ at least twice each for a total of $ 1800 $ yen: - Go to zoo $ 3 $ . Pay $ 700 $ yen and see animals $ 1 $ and $ 3 $ . - Go to zoo $ 3 $ . Pay $ 700 $ yen and see animals $ 1 $ and $ 3 $ . - Go to zoo $ 4 $ . Pay $ 200 $ yen and see animals $ 1 $ and $ 2 $ . - Go to zoo $ 4 $ . Pay $ 200 $ yen and see animals $ 1 $ and $ 2 $ . ### Sample Explanation 2 By visiting zoo $ 7 $ twice, you can see animals $ 1,2,3,4,5,6 $ twice each for a total of $ 2000 $ yen. ### Constraints - $ 1 \le N \le 10 $ - $ 1 \le M \le 100 $ - $ 0 \le C_i \le 10^9 $ - $ 1 \le K_i \le N $ - $ 1 \le A_{i,j} \le N $ - $ j \neq j' \Longrightarrow A_{i,j} \neq A_{i,j'} $ - All input values are integers.