{"problem":{"name":"Get Everything","description":{"content":"We have $N$ locked treasure boxes, numbered $1$ to $N$. A 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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc142_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   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$\n\n## Input\n\nInput 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}}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc142_e","tags":[],"sample_group":[["2 3\n10 1\n1\n15 1\n2\n30 2\n1 2","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."],["12 1\n100000 1\n2","\\-1\n\nWe cannot unlock all the boxes."],["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","69942"]],"created_at":"2026-03-03 11:01:14"}}