{"raw_statement":[{"iden":"problem statement","content":"We have $N$ locked treasure boxes, numbered $1$ to $N$.\nA shop sells $M$ keys. The $i$\\-th key is sold for $a_i$ yen (the currency of Japan), and it can unlock $b_i$ of the boxes: Box $c_{i1}$, $c_{i2}$, $...$, $c_{i{b_i}}$. Each key purchased can be used any number of times.\nFind the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print $-1$."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq N \\leq 12$\n*   $1 \\leq M \\leq 10^3$\n*   $1 \\leq a_i \\leq 10^5$\n*   $1 \\leq b_i \\leq N$\n*   $1 \\leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \\leq N$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$c_{11}$ $c_{12}$ $...$ $c_{1{b_1}}$\n$:$\n$a_M$ $b_M$\n$c_{M1}$ $c_{M2}$ $...$ $c_{M{b_M}}$"},{"iden":"sample input 1","content":"2 3\n10 1\n1\n15 1\n2\n30 2\n1 2"},{"iden":"sample output 1","content":"25\n\nWe can unlock all the boxes by purchasing the first and second keys, at the cost of $25$ yen, which is the minimum cost required."},{"iden":"sample input 2","content":"12 1\n100000 1\n2"},{"iden":"sample output 2","content":"\\-1\n\nWe cannot unlock all the boxes."},{"iden":"sample input 3","content":"4 6\n67786 3\n1 3 4\n3497 1\n2\n44908 3\n2 3 4\n2156 3\n2 3 4\n26230 1\n2\n86918 1\n3"},{"iden":"sample output 3","content":"69942"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}