Problem:


Score : 500 points

Problem Statement

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}, ..., c_{i{b_i}}. Each key purchased can be used any number of times.

Find the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1.

Constraints

All values in input are integers.

1 \leq N \leq 12

1 \leq M \leq 10^3

1 \leq a_i \leq 10^5

1 \leq b_i \leq N

1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
c_{11} c_{12} ... c_{1{b_1}}
:
a_M b_M
c_{M1} c_{M2} ... c_{M{b_M}}

Output

Print the minimum cost required to unlock all the treasure boxes.
If it is impossible to unlock all of them, print -1.

Sample Input 1

2 3
10 1
1
15 1
2
30 2
1 2

Sample Output 1

25

We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.

Sample Input 2

12 1
100000 1
2

Sample Output 2

-1

We cannot unlock all the boxes.

Sample Input 3

4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3

Sample Output 3

69942



Sample input:
2 3
10 1
1
15 1
2
30 2
1 2


Sample output:
25

Submission status: Accepted

Solution code:
import subprocess
import gzip, base64, os
import stat

gz = b'H4sIACd4j10C/+19C3hTVbb/SdJHeDUB0VseSsEgRaS0UEqLoi0QOJEUKi2IjnhI05RW26STnEDxCbZVYqgyjtfxzp0H/5k7/udxr+Od/4yDjgMFlOIbURkeooyDemJFig+sOpC71t77pPucnFNg9Lvf9/++idKd9TtrP9baa6/9Otn7brd3gdViEdSPVbhaQMoytpzQ5Qzf7E+xAFYqDIK/44SxQhbQmRxfuVCuCftY0mpoZ3w2+JcB/0qtlC61lmvCsYxPDS1cmCnwn3JN6LpR0ISCkJeKh2U9sJKiB1au0oS5GRQvzNbGs7J4fSxeH+NXQ8EqaEJVvgz2r4bhNUwuNZzP+OZz/Pipek+uw+8N1ZRuqC7XhJsY3yZdvOsgXpZw7h8nC5ey/Mz0ks/Kr4ZqPUxraqwtKZ7WVDe1qTEYbZ3aWloytaS4IBIqmE7K5GS8Cxcv0+gxl5V5JLMBfL5zyqU7C0atqH+hadhVR+PXHxrzwPet+Gw2i4dV0hF0NmSMH2S1CMXCekgan82Bf3Ph3+/emvHm4A2bpR/7//zcA83JPRs7/Be9Ub2lbdMN5SennpRuzslbU5jvftPb9eFlXSMfHTrvJ2Nbtq7z3PrkQPo5BgUYYYC/bjXGp1mM8d8JxrgzZWHazzgT/NVM43TuNMFfNMm304R/SZYxnm2C32yC35dhjDea5DvVJJ1SEz3/wQQfZZLODBN9rjZJp8UknU9M+C8z4V9iku/3Teol08R+akzyfdqEf5hJeVaZ8C834T9lYv/jTdJ5zKTenzLBnzZJ/y4T/TSa6HO2SfnHmeDrTPQ50oT/cRN5m03KL5qk85GJXGUm6bxtojfZBH/BpJwfm7S7SSZ62GeS/ism5awwkffPJvleCumMF0YLT9SyfpfhIxje61+l6Z8mZVJcqKP4CoYPyWA4S2c9w3/B8t07qlyT70Kmny2jtfgiyHc4pHOUpa/a2G0ZFBcCqzT93kELzXd9rZbfwfTZosu3KpOms6VWm84clv5RhjvZg4VMrlV1OrmY/svHaNMXoB+OyHX+KVOw7y0RJGl1cygoRWRfWJYkQbp2jbQ0sLoxIgfC85p8kUggIkiemkqpLhBmcE3lvKZQMFDjq20K0GfGT6QWuSEc8NVJtwbWSX74JiPob/VJ9eFAQAq0+gMtcmMoKEg3Lq6OFEO2LUWFEuYUkcOhde6li6p9Hr+bPA6VwYPGYCQQlj1NbvfS6lCNhA8WVcsz/fK6lgAwFs0AnrWNdYEgcDbK7jXAUC0XzZIkKEdorVQLRfE1NYX8a2jMSNGM+sZgnVTfGI7IUqjeXbXI39xMs5tZ3xSNNKhJlPBJ+H0RmaQAD2aEo0G5sRmECYdD4flFXIQQCBHwNauF9gNa5G/whSU57GuUI1BekAJSqPVFGv0qt6dGqimU3NUlUtWi6hlSE9MXyZykXAZabm4MgippESLzilBPEVLumhpIsKw/wcbgapasQe5Et1S5cmljKAKyRQLFHlAcEwPwElCWrynQD+gEZpmnSgIK5CsNoWYNIrPSQX6GGpnpbwr4wm54Ml3yQJngn0zMBkSfXqjWQiiK1SWFfcHVAchSrc0SUptgs7IUDGkrFB/P4ipb97zGAyXj7REBnaysKmrB1INgA7K/gbNbKFu1FGhukddBW2iBxhQK+1YH3MxCi2ZSqWmV1EbrzetjBvCgsqXVra1SSyAcCQV9TY2Q7JpCpsBUMedPZ7USAWVVSqC4WyVIsU5FS3wtLYFgHRESkLqmqjVQFXIZyE60KKOcy8+rdKQeiv2g//S4YGYmcTFacG0ziTyL5c7prgxUR72Du7lZYywps6SiEv2TBgy8OvcRmtESld1+ZqXn1wbASrG2icEtAZU1h+oCRL7F4I4g01ZfbeOaIjS/SKPkR58ooceBll0fcvPOqwgkYe2ziQmdpnFgnhUOgEtYA+Iatb55rLEt4uu6eG2DT9ZXLGt6WLHo1JupP4dvq/1QI0gVCdKy4Fo0+6WBSLQ5gA/9lK0+BGkIoBo51CTUB0L1Qv3qgBwR/ETB+KAJnjOdy4HWRlloDjT7m1tI0LJOqPc3hSIBoZnyA9gcWoP+HbNgvUmzrzEooK8XFs6bJ80oKBQWej1z50nTC4qKU1+nF8wU5q1YUTHXIxUVzKDwihXAXVxQVKQhy3iKzPTwPxubLVphlmiFmT7+ZyXf6F+Bfc9MxcDvNvbcCnNMK1uToFxZjD+LPc9moZ3jT/8vC/ppi3A0s3+eVnXZuiE4E41mqfNgq3CaPS+Efw9/75EsnP3fmUWx6OjGQViKjSn+DNL3q+Oa1397aybOiB9m/L6+H1hxZvxTRsfunmzFGfLjjJYnP2RHiZ9h6fVJdHyQpV8PYeOJTDY/Vj/rOXwuh2/h8Pkc/gSHz+bwoxzu5nB13Ib4lXx56vrxq/j5CIcv4NPncM1IJ9CPV3Bw7iqKZ3NjKzIu43Arh+dzuI3DCzk8g5+Hcjiv53IOz+bH/xxu58eBHD6Iw1dw+GBePxw+hMMbOHwoP2/l8GEc3srhObw9cLiDwzdyuJPDN3P4cA5/lMP58f4WDr+Aw3/J4fN4e+PwCzl8K4dfxOFdHP4vHL6Hw3M5fC+Hj+bwAxx+NW+HHD6GwxUOH8vbP4dfzOF9HH4Jb8++fnwcB9s5nJ/vOjl8PG//HD6Bt38Ov5S3fw538fbP4RN5++fwy3j75/BrePvn8Hze/jl8Mm//HH45b/8cPoW3fw6/grd/Dp/K2z+HF/D2z+HTePvn8ELe/jl8IW//HF7E2z+HT+ftn8Nn8PbP4cW8/XP4TN7+ObyEt38On8XbP4eX8vbP4WV8PbZ9ZBfjmW8uzBPEji45U/ET8Fn7Lu30MzlzJ7AkJz4Lfx3jyuEb0g34KHE0CZ+JTyONrjmxl9C/QxpdcqKL0L9GGl1x4glC/wxpdMGJLYT+IdLoehObCf0Q0tjtJdYT+n6ksfiJFkLfgzS63sQqQt+GNLrcRBWhw0ijq02UE/oWpNHFJgoJXYs0utZEHqFvRBpdasJJ6KVIoytNCIS+Fml0oYneM0jPRdpJ5Cf0bKSHE/kJPR3pEUR+Ql+O9AVEfkJPQHokkZ/Qo5G+kMhP6BFIX0TkJ/RgpP+FyE9oK9K5RH5Cf7UA6FFEfkJ/gvRoIj+hP0R6DJGf0O8iPZbIT+hDSF9M5Cf0PqQvIfIT+gWkxxH5TyO9E+k8Ij+hn0Z6PJGf0L9DegKRn9C/RvpSIj+hf4a0i8hP6B8iPZHIT+iHkL6MyE/o+5GeROQn9D1I5xP5CX0b0pOJ/IQOI305kZ/QtyA9hchP6FqkryDyE/pGpKcS+Qm9FOkCIj+hr0V6GpH/76T+kS4k8hN6NtJFRH5CT0d6OpGf0JcjPYPIT+gJSBcT+Qk9GumZRH5Cj0C6hMhP6MFIzyLyE9qKdCmRH+iq7RkwclLeg6/bcW1qG5JPK9DqlSIo/opdRcc9sdduFmPvim3HeqtqPN1dzqpyQezesWUJBt29Y8sFZT9E/8wxDgaIW7+AqMvEqb0QiG19OWLsvbXWlbu2Ep8BjuKzldvxUfKoYxxZutray/Hv6LMBvxjbKe748BrRsld8rS8KkZ+mkfdBZDG2m8Z/l8VfP+dGEYwpOnwZxFTuAgFX7s5cCJDl013ob8S2OfkVwCBfkirCyGXbe1dCbrH3kntXJm6HKI5xQiJCw2UV11csr1hWUVMtbvgIN7W2Y1PZhsNLxQlSirFd7qJTYsdhOV/sfNi1GR+6UCGxdxSsL7F7nh2dGYRkeOSJvc2l8MrXmMJzYsdxeQ5GfxSfvEain1A2kOhuEk3snu8iTlKMNblaAbWjRwSQPO0Z3f8cvrSSDsISg6dFx72x37tQM5Udp+QMT3KB3RuTXXlcGa79mklxDKWYKnZucm3Bh1jqpweTLN9ROr42EuUtb+w/XBvhqzceJSXLdd9fwCV94isiHoccAcQT6y46XNmRlKdXOJ58rq1vWdTmSe5G8X+JScWS3tgppR0y9HQvJBlCSDL0xr72xqHwnvjVYnyG4iOpuwUs9mAxucjuaL86C4vnZsVkqoNyNXjjd7hyxbY7YfDavhOc++75rhZLHBTU3hW91JNcYo9e7Ilni52tylM4oxDLXnV0HMoipVF+9WUyidoDvsWEL0vLdxPh+0LZAHxi5x2uKrFTdjUo94DPQ3IFklXKpRdSchWSK5TiC9hT5dfgG8T4TRAN5LgC5YheJsZt2jwuzaL1cDHmAVVcRfQByliFxYm32sXYHa68bdiNKaNohW7PS2l9NcQqeh5tfbQYy91dbgfllDupkspzqZJ2iDGvK9cbLyOJiKCvPOXVr/QpXXyuKTm98fFiGyQiOB44A8+xkXTe5Cr1dkJtiPCnPPE9MkLo6nuKNsTn5fKnsIPsdeywxza5XGDgcRr0FGjYZpmxTYzbO69LxpwdzzsebEfmzt+78uCBkg2l7olyT/fwTxN9yWQCN3eJf4i94419rDw3FiU5IcbeVm5hNSWKgN85nODK51fQSisdqNLGJVF97ygNX9BKI+MoEaxOFOMQCotiGV+gKvIhRcy0aizNqRBz+nQEzSF/oByOnaE5ZLEc8tUcCsV4rhhvsItlPfLU+vr6Ase4djpOA+586M2Se3BHUNi4Q3z93UWWkZ+JbbuA+Uj0HVIA5UImn4i5uyD33OglYvxKEVptpvLoKZrr5lM0V5F4g+Ru75XQOEndkqp2bPotFK/fSIU/Y45PWUkpdvaMIv2DGNsv7vgYnPt+8bUzouO3z4uxT07ttMgZ8D0hdoYtYtsZW+QgWNy6HLHTbQHja4NewTEvwVnlfaeYCzuOxZ0kdl51nMy9phHctnuenTgt5rxyqfM64omD7+gmWqmMX1TxJ+JqnhKODSHvYLiLunoG1W9eHBt6wJPc5YnPFmNfkbITvp4xrL8ZqPwH+fIn1w0VOxcB+aXN45h3wFN2+I6f0wZyV7XYuSwJ/dld1xadKnq+Z2jR8/315YmP/Uwc9CKoW9yRvEYcf0K0vAPYF6Jt7B6xbGzfXRlibGyfmNwhlr0Q3SeCH8VKiD4DRqD0ecv2iN27sbWIDm/vdlyLoY4w3uRyKv/9GeDxzMHXwJA9Xq6I8Uf3+lehN3W0/xjGz+tvLxXkzPvnzesZhZW9i3DbgLNwG+sVknsd22iqSgcaYKxbmXoKfeVx9JWVTvSVdwpoM0Mr1t9pF6KZSuXnYBHQfpZhasA3QUS+sSLjG8LYLvsckzuhFHyGySXlCeCigc0Tv4aldjdhS36GqSWV7M+oh3aBhwZDxf6BGOqJT/H5F8oHn1JDJVMXNPAGpR1GiEVd4oZnsU//TsVNFSsrbq6QVu7SNTGirugSVMDPMBFoEg2GHQxR27+jd8aOqON7+E1tLwc+p+1lFaSQWItPOHfmaP83bBXGLi3RrvORjvZN5tw9t2lZ7xmAtUXjUu8wY7uFc5pfoLNRnebvUZb3AOEZ+jiG7xOGPg3D7C85hjAy5H+pYejkU7gOGW7vwwHDbuqV7p7U75X6DdnRXgzVgT7K0XE5flP13nuS6l05yfmpRLYFW//uxOfEC+zuGcaSL1fyJvU7dUf7mwJJFCrzReJUta63/Rf63utuMx02Y27uJJWDeXQoc1K1lcuTtGVpksdSamvzyABmgv1ZSo13D0upMOcTqoH3e7keqF9zA7TA/zhJW+B/9g7YAu88SVtgRy9tHKuM+ouGXmb/vWnN8PR4Onaa+ClnB5wAlawKJ/ZyHVyi7zTmClJsxwaoHDiJun1W7G53PYFLaKBD0uG0KGLb7pFi5zMEVk6eQOOixLbXYZD9NM6ilds4WMThpaKA1rgx62RS/F1Yax2PE/ui+RQdTrzIbGkard2ULa1Q3nD1j+oc7Y5UZWcaVfbctMrOtZhXtg2eKcc+hsZxAxmf9XhjpyHfgdzu/hPU7b79MZYThjVHyGScGCQVRlugDpvOuG8xM+4VkAZRE9bSONBU4mQ2VikO01NPTiiZ+OS+bKItAqLR9EKpUhx/AyJxsY2zY8eDZ6zcMG0uMnxkNTb0iSeonZw+zo2PE4+eRmUzAWM23kD0k5mtBOSUIF+jUcAoMwVkGxXnEdRzd4ardymMKMG2utCYiK0OJQ1lCrS86FQsWhexOuh9O5/JwO/x32cchaDtFYviA5l6LkXzIs4AdDTtY2qqJFLsYxhFKZs+ph6TjmifceGsVrn+hMaAG46TSRc0Y0fHaGbAW8kQJ5kooRYM44CflcA4IKaWaNhvStiwILaJFAyVh5k4obvHBHA09a3pq55UG82ghVTEMy7cnlEuZo0T24Ny9Dha8QdKH4Tlf7CQlrU/5aVfMvLSv03rPzsG6BQjqmY8sWwszlbVm+gmomnG4mj/Mi2jVwfw10+b+OubP6JmXNIDErYfl+0o7igUO04n2pUdxxztf7TicNvrAqH/E7/GM1zfWk281UN1/PsPaY1sZOu2ibkmLe83PWQUWVessZ7m4v9F68nvMbGedz7irOdnwLU9P9Uoqj8kaxMwBgS/Wem4vssx3J0a0m0nE+mWj9gCQ6cI8+tKJ057h3pjpdgfZniSCxG0Q5RcNhrMo6NBxROb77Jja2t/m0yMlkBFvUHG8toVhvY/phlN5wDWeTtpp9SzZyoXJDjn+diHpJeGQcLfoamTDF/Hb/oMf2XVZ3i31dxKbzGp8q0J2ulvVqiXy6suF7Z1gat7+ujicgGtZzdRbpMrl+8dLAjGf0RWo3CYcAuZ1Nbp2uw3soRLErT9nPqAWoT6Nhz2xK2Y52qSp+/bzPPXCs3zng9o19OqZtigjoXs3FjoJVbCGsZNFu3YQtQtOHPPFZOiPSrRr/Fvr5HYsJg48lMOvo8zEJx5yiJmk0dynEO/6nJcqMlxvFmODhzD+RLGY7jYBzTnPEV6n87HZiXI2KPoeKL0K+M4yz6gJjYVYiTsX+FSLJ0Pc+uxbR/lirFPxdhprlXfCfzQrWFLHU/aNFmfEtj6FFunyqMLAN04hAQPCy0qdoWLzG1B4+XQqqE6xLJdjvYxEKGefDTrJ0ouRn/WE7/e7rnyeqc8Bteibd7YBLFtp90Tu96e2Amc9WR9ozI+TYzt9U5WcDEbZH4Ky+B1zD/psex2PNTljZ0UdyTmOP51h32HuDVJP+O8DncvzGf/TF7gvawf95TtXnv7tZ1XfU5WN177gHgwyAFL4p38oSf2F8+OpA3yE9uO9okWBQuVh95qCFthCoJ6FnfecdqOg0U7jghfOoaVA/5KjOV7Y61Q/O5rO+d/DvItdNI1oZtghkWGrVjLp5UxkGuiFcmLROx42p7N5abPwEGGysflSTCvyI2O73dYtcfojOJGkiPE7E4pdNIHWMHr0+q3wRM7hfXbP5T5MUlkFy5BHpYnip01rlXb/sSW2697L32NWowdxNXIfC6JG4/x690kjfJUGsPeM1znJivO2WJbqyI42v+DzfmdnngxmM1ipWif0kETFdu+Bif8KPH1V3vj13hwsYYyid07sQ6VMX9D2+fXxJ//G2sNUOWO9u1kofs4rnVV/JmMM9AS8WcAW0mhJh8QLc9hocWiU6jO2/9GcvZ23portp22RKsq7s+u2OgWepaRMuKSWFJuFklvdbqnjsv3OoiJj7vkxVAXdFBcziRnbSb2XM90L5rOGTH2odIFytl6lBWpw5EJ1h0r8HQvYGOjBWyR/nMYpOAc0ylPJKMUXJDRjlAcHaEMgXQUle9qOuVt77LlZU/sI2+szmU/WysWYzs8MUfRYVxlzMf1W0+8BLUNaYuxQ0oBUc5zJP+yFYrjniBObGIJcfJBslLvjb2PbD84phkvl76rTvjkQmwbVWTuAKHpxKHHkfIPyF90GHVfqhU5aiXeoDIetVdeGQXl4IpVpid2SdFhT9tue2Usak84rczhcP7mJlehJ74StNWLdU+8SLfqRb70WLqJF/nS2Iv0QeOnXmQK70W6Hfe1QU7gSU4TT3KfqqaVAhaPZRXbIbb9FdxIQnaI8RpclR4OdQOtqdBb9qmj/SE2eBF3KDYx2QVMJIIF1Rs7hE7xuJwjxsH1VIKybHTOX20XO2HMBNrJE9v6rOG52K0ME+NWMWYRu62UaS4wvAJTd7vsFOO3AbEORllz7fQ1gy47PgFPKILrjO2MbvN0LuhDlw2dwZGeKm9nwJ74kX5t5oL+jsvruikO//hOcg7dkvnrUXBqRTp/740HcNAtT6amPEFvytEfoBnf+w7ZqmNvQjwHxfs4+hztwkGR6IzjILG3sy7fCQrGvTgcIBSiC/5C8byD7b8ZGlPADr73NDgct5M0IG8cmgCYIcYuJSYujyPjiVG6AUz0RnReApai7TQMeVdaHB2fwAAw8Zvz0oTjwe/gjJlo43VILOE9rV2sPFv0NUk1+sMYfXUSe/E67GRRmhgIsH0beFolC5/KUEDlJVB6IgLZJKotZHojj6eaHp2maQk1PfZtutQ7jmzGjdJtxkVvQoX2HcFs+6BrauBXdnk5guly1GoYbk1nkDQMDekMN6U6nSn3Z0Ym5Qkb50/JTRz4SrPEmfW1qqLvgiiJL7RPR6UUWI1PByc1T8elns7Ep84kXXTvuwCdqUbN6Lm/i3+acHsZBnuFguyjG0M42FvO9oi0g72S82gzg2k5/usIHdsVKm1v0W9O5SDukUGWdpalvT9L+7eQ5WyWpV1xkiy9uKD6vNwiJj12HEKDA3rxm+ax/y06Sn/8MB2z3Ps2cZCpqUzJEYoHdfglgCcaWbX4cAcPwhtI+Bxb9vpC+fItNGGYx+P7RGwePxO/6ufx/0DBL36LTt8/PwQFwfeJNO8v2MkC3Odi7CoXWRl0tB/MwKHKnc5tW6BZFu0jG1xKH0rd1gcjmVmZmhcexh3u3/01GzHsIGO7mB1G4bh/5tnQLeB7DGrvc7enMyNbnJO0YZqQeYXD+wXZiIs7sUd2Kl8fwp2hLrp7weX980Nqp0w7tHzcEgOZnfjigJKF+wWHjcZ/R0h54qW4p+o4QnedLoexqT0KqFu7itPxEltoe/JgMknH77RspcoxSBxK1VGGM2hI0RsvJGvMDQok+CeSlWPxkbbWPqF1CFZy+1tYoVlkiiF2ei9O3j/Wzknz5kH1xY+KZ2j/7Nj2OnnlAnedOze5elEixyHSrWh2m2BkVBk7wSV1/0GdYrY9QwezqJg+TKb0kKFiPPGrQAXXK/jyRmVnUPFcuVyJOvDli+5DRNiHd/VYYSgDCsslChtBBn+esueiK1BJ3ztA7FjOJjYsX9h+uBJGmFO1/afeqIElOhcttBpit5NdHLujfT92AGSxpG13X+rFnAZiNL0Vjh1ZsXZXBhhvnAY912taRj0/LSVsNOip0bCtMmNbXBHP6hSTFbEcEPrB8aTTOoFTUXzLUXkBCpoYqnXEVybpqith+BUyTNYy/PE0x7ARGX5xmk17NjyLzZDrmHBZp+O4o30vWcqsBG+wmwwkdcbZfk3a4s2FusUbTqgEvsWOWxJ3csvwPbfy6zHfZfX3Hdrh1qSN0ts/SduX2GMxz/H/WfqX9zH94QeYxDCthqF0Ixm5+M9j6YWvI/2aBlHstL9QN529XzOlxPb3BmROd4ee/gttH902dTU+L0Ndjb/rAF0gJEgbbgnhi4zKrL/Q2svPoIvqeNiDYj2gmSRcsL9/Uf07Vrqojny4qL4W3xMjGcxJy3xjppq5hWVOkJ9j5v9CyrufZr45k2a+HkKl4y+azB95sz/zhSxz5MPM/emrdkRZ1v20zzr0Blhj3Zm0dRfCdORN2n/8AZmuAaYesr9Vm9oluOMSus6LGhPjwzou6V/nJVB3O9Gaus7bkqHfWvrvtDXP+wRTm+qJ0lyzWK6oKsjVweVKIMgV1aXmeiBTt7p8t8bIbjDLbaGRSl54g64loljq6vIqNIgN+2n9tSIxHxTXc7VR/PtZfCygGn8P1mkFi48/G1Iy3qSmPJaFrjfpUtnQ/XQLC02L7Urg13PclTj79gcvfkQ1I5YRfj3HjF5K8xQ/G8BTdFqMTVR6newl5I7V2Nj4sednY9/Ipby1z6S2v/8GV9vLX9csW2TvO+teguuNf2wvQYzNo1sJdVZ1K+FGq8FWwpy0zuGCAToHfCMvscGkFg6+RmrhodGaNvfvo8+zzX2TWlj+mkmbGfY612b2vqaphQ17z1oLP9n3DWthqEWtBavFoBbeS2tvfzJvb4nHBOZV1SXSa17l9nT27WV7Ou99re7pHP7aYE/n12l5rh+gjQeN1P3Bq3S1ffsrqHZbFe7nOKG/6rnCiPspxv09yq3d/UHftWevceeynkVcARETjq/J+9UVy8lCvid2xhO/OQ/HCVPIOGFi2ruOv2aLxaNfwV2nBXQRP35z7kBxfsDivP8yiZPL4jgHitPO4vyOxqGD7vglGGUCiTI2tZmTfJU66/sIaxZd/cH18Ju1qw3L+KlbBkzdMno8GobreIahwDC0x61hWMwzjASGkT1zueEmeQ+0s9ilXIyq3a99LevrM3TVwK4kX8ZXKLRPh7M1BafyV3xqBZIfvy/DCtrw0XoyADhDpjy5WKH4C53U2+FfQEyx7EcElIfCCBfZQQsrd+GLoHYy3EE+B9r3NBzpTGbIyy+TaRIdIqJmyRoBvg5xR4Y9Lmfk44sQaC89uche8DJ9xRra6dv49sMDQO9ud62F7CZRHIqGFHm5VQm9rA4C//Aye42MTBivcinFr9B3CEBp2M0GXsK18G34K9an8cgPxCyv0LFbPPO+C9EVkqIN+/6Fqh/0ZthxVdhJPeB8fNH73NzfHRbSHjFIc3+tuFV9/Ut0c9BJfd8dLlEZ+QqVfJVy6CVqdJ+8TIrXs5KU8dxfAThr7gdfJC8fONqtSToGeRRyTHx+Rvd7iCqwh8r41cRF/ZLuc+c6On5CWss4TzxE3j1eU/EMFqmn1Hwpg7YHriSTiCVXQyl6xm72xqfgXtUED05Ax3rYpMhb9kH0v3D7atgLxAfRlkffYH4ZssfGakclHX+eupz3nudbqJ2bfenWe6vF2Nep0frtdmUofYf7O4m2F4n8+ucfsTew615kfLc/jw3INL1nGH+xyr9oYP5NjD9D5R+D/Cn2zVXKD+GJEngBSzdfEKB6YsmK5Z7YqYplntibFTXezol5OXnCMrFzaj6E1d7J78GcfsdpG/5iT3HvoSsil6TWu2MfemOn5kMayZFvgUotUIvRD4nOVqpK28WV99Nd7Ld/7Kd++Dv3aXWBNdMicl1jUGgMrvE1NdblNTXKgbCvKa8+FM5rCgVX50/OW9soN+ThuQd5RYWzJwn8KRSzZ+OhEKEgUFG/nBeMNjXlBUNyHklL8ExbkhdqgeTwaIQ8+J8cRVCXV9/YFBDCU4QFEOaNR5YgyQ8PoYFEhbzBukwi0Vr4KswLRZvqgpNkFgNj9/9ecXHRdGmhd8ncCq8kLZaKSlvWyQ2hYKN/Jp4BESkqXO5rigbceEKI+1z4Z1TLvmAdHtPBogzMX+ZWj4Bwn1t5ZswFhfKRnOq5QNeVa353n/qdMHtexZ4/cV254fM8hu81ed5bxdLXPR+4vLM8SzjdnYN8Je7gmsZwKNgcCMq6mNryrFpqXB71eSF7vmVpueF5fqoecExDD2hj8o8y5u9aquUvPAu/U8e/SsdvGWO7chP7Tf2BZ5PJA/jbZGisfTCq/zcI0eNuBFeQBx47951kcgWEfUeTyc04EfswmcSFGuVUMpkL/Bv7kkk8H+/Rr5LJVRC2wtDrUaQhfALCPRDugbAPwqMQlv49mXSCT/0lhCvYoQcj1fM0b1sqWFqdljFDs+2bLdnOkex37YnuZJL/PbYxP/0NOfL37Uomt2DaOc4FObnXOoasta8Xrhl95eUzXBP4czxtt1V5SQrZNjzKyqamU8x+j74KdLHxQkHIeGt5uVCR45ybkzs3J29uTv7cnMKKnNKFOUcz2rI3ZXVmPpDxoO1eK4l3E85hjySTeDZXhnOFUbz5OVWaaCTew5gf6LpqEMTzmsTbYknLD99MbFWSyR8PhXh9K4zL2ZWjiTcyJb9Wf2OZbvZ8lkw+jIOcuTnOipzc+TmFbbYHrFQnV6ENQN0PwxNC9t6g5leRk7cwZ4utLeMByADLVYd2CrbxGjmYLa1MFTnlWh2o9Yrbqwcg3sUsHu4lI/57tGfAJ+pwlL/PAD+G9v1lOv531NdzyeR4hqvnnuLvcvKAPyBQuR+0unNyH7C5c/I6M9w5+ZsyxZzCe7PEnNK27Mqc8iaUAOTIJzKBZCCfnZYf58qQjlXXJpO2x+9ZL9h+Y53CDpUYjz/jvoURJUicZMdBzMZXxxst9KyKKnwyzUoPxpiAPwW/mhGXI1HJiGlI9Nro+Rz78RfmXzPibSSyMuhJHH9DApccUO75OMRuYU+8SOzNoAeFtCPbizCiwTfI/g8mPQPmWA+qZ5HsHEJ/538En/xgKD2MhLDNzaEnb2zA36TflkOPYziGxFPwZ456yMmp4fSAkU3Im38BjXPDhUz2xdaUzp5cDzorxjknvhHwU7TJEfDn1tSJoxZa4PvxSQf8qenX9y82YOQfWaay00B+iIzfZcTv7MymsBjdQFgOssNHXkXiMnZC31+QrRQIh3qeC66I5rCzeS2NVqrJUvzJv2yjZbkOiddAJfg7dy8SJzKpir7EP5/Bn5tsmpOEk7bXNwi2vYQ4pApwiJkGvs0iDGJy/hwjyow4jcSvLPRsESuyfWqhcRxI4K947WpGTnYUYTkOUydk0vMqrkVicSZ3aIZ6IutcfPJTxtaFxItA/FFN7Z5BVHGj8Y99CCW2oLWNgD9xS6oO9gq2xeREYDUD/NKCj5DYwZ/T8jo7jOYnGPsdduLIzy2MN8ci/PPzz88/P/8/frrY+e1H2XmhW8Zqx60Wk3B/ppY+qqNPM1o9eyo3l6arnjk1ks0bRqnny7BzxNUzlNQzpdQzmBT2XB0fqmdmfX4mGSLn61jLU+d+EbkGlafOPaMDKkqrZ2ftYQ/UM7PUM6Au1OnH1n/QFjtxjp1HlKkd76pne6lnTHWNKNfgW4eXa8ptZ4oapMsfpv1EnlzGn2S0Wo5eRm90lv+v2knqHHv9udCsXutZuIaF97LwERY+xsInWbibhftZ+D4LT7Ewi82HLmLhZSwsYeECFi5nYT0L17DwXhY+wsLHWPgkC3ezcD8L32fhKRZmsfN/L2LhZSwsYeECFi5nYT0L17DwXhY+wsLHWPgkC3ezcD8L32fhKRZmsfZ4EQsvY2EJCxewcDkL61m4hoX3svARFj7GwidZuJuF+8cY29HCefNm5+Uvq40G5WhecUFpQfHU6VFCFd1VVFxQWFxQPJniAmPyN/mCq/PWBMIRXJ6ZUTCzoHBqMY0y/S45HI3I66bn5cu+1ZFpS91ed0W1W5oxs3BaPR6bOTkvH1eE6nBVx+tdXkmjTxaEgsi6ZtlXC6EcpmGD+q0xKAfCLUJBMCQHCirmeqZC0oxaHYwW1EYbm+qmNtYJhGrwRRqEgrp1QUiPhnKYPmEF1hASPAsHmnzIyL61NMmYZSP8lQOt8BfK3QjPQnU+2ScUBBqk+rCvOSA11IX7KUjU72dHlkoyOR6ZpCH5wmHfOpqG+v0Wf5gUzNfc6Id4IZn8ofnSPGojEaHAH2rGNZBv3J7HMF+t+rP+ezUEjZ/V9wOp87l1Zyb231shaM67Vj8ZOrpIF19m8WUGuM4SH+eFMNUNqfFV//8oA+oYnqnrL1LrTcz3W3X9g+pou1j/kMVkt+v89HLGatX1N12DtP2Lmf5uZr5dja/6842s49usK7/u+hAyzTrDxVf7i1x26OIWob/8NgP5b2M6ter6p63Dtf2TXn+q/O26+Gp/1zVC2z9msjGAPv4DQv9dK/z4IDdX2++b1X9MF7+cxS9n8bfYdOtuuvBhXXx1/HOUDUCmFxvHVz8/1MVXxzMjq7T9uln5t+jaXx6Ln8fii7aB8/+lLn7//S+U3nSW/J/Uxe9j8ftY/GO6RRK9/XTp4uMyHA2Ny6/Pf59A5+o23fhPvV9GL68+/7fZkoBNNz5UVhrz6+kPWflT4yoWv/cc45/g2hY/PlLv/1EVk6WLr8rVp8tfPae3Txo4fzU8rYuvjk8FFhy1DBw/y6KNf5Sd73jUd276H8oWOlL5s/N+e1l8u67+9f3BcJZ/oQ5X499r0v+o4XBBey6v+llTy/yHZWD/y9su/6li61et7LBbPMBwiYH/GmSS/57baOgbMXD+A31swK32x1rcmupntbgt1X9q8YxUv6jFM/v7Ow2elerHtHi24XzDBlpR+x0tPijVn2jxwal+QosPSfl/LT405de1+LCUv9biOSk/rMUdKf+qxZ0pv6nFh6f8oRYfkfJzWvyClP/S4iNTfkmLX5jyN1r8IsN5lg1mlap/0OK5/e1eg49KtWct3n8PihYfk4ZZiM8+mdTj9MzcdD1cw3DcVuE/1zHcq8P9DO/T4VGG4/YF/7mPtNf+eh+v6UdHC5m6+1deZfzq/tpETjDEBR1ezHB1X049m7mB4VXXUvxhlsFDDC/UpbNdTZ+l8xrD8a08Up5iilexAcLjDH9iDsV/zBZMqm0UXz+d4gfV+/EY3ruIracwJ3ZpBtVDhk4P0wnuSO07qv6rluHqfqeK/yvDe3X4HoZv0aVzhuFdOvzyTIrv1aWzguHqvrF6NvNGhqv71epZy39ieJ4O/5jh6n6venayK4vi6j6verZ0FcPV/W51z/IuhpdXa/kfZ/hRXTp/ZbhTxz8s27i95OJehEF7n5jN7Ee33jab4at0eCXD9etz/mxa7xZdvYcJnu5//o2l06VL5xeEP92Pmcn1LOEfLhzQ+YF9JvIKJv7kbcKf7sc+IwtnF6SVP9NOcX05c3FryMB/jrfj2CPdH15hN753apEJvpbgwwQns1t17HAfwy06fT5gN7536mWT9D8xwUcPMr7PbLIJPmeQcTrXmeBBE/ynBE/vT39hwv+CCf62CX7SBHcONsavMsFXmuBrTfAtJviLgE+wDhM2M3+urgu/O9j4Hq+JQ0zuIxxifL/XyiHG9YW3hQznxifqPGmjSfr/1wR/ygR/3wT/yqQ8I4fi2D+9vYwfapxO5VDje9TCJvz/PtT4nrMdQ43vezuG/NZRQq+uPL0m6TuHGd+XNmmYMf/8YTR9RZf+dSb8gWG0vW9hdhJQxy0m/PtM8A+GGd9jl5ljcg9fDvKMTtPDDBP+xTnG9+G1mfD/3ATfY4InTPDBDpP7Sh3G9+q5Hcbp3GCCN5vgT5rge0zwow6qT3tAq8/3TPgvdxrjVzuN7+FrNeH/idP4HsGXTfh7nLQ96uv9E6fxPX8XDDe5F9MEv8MEf9QEf8IEf2W48T2Iigm/ZYQx7jLBZ5ngy0fQ9tjL+t+NbAPvOwQ3mFdOC4dC8rSWdT7ZH6oLhKe1hEO1TYHmyDRfrb+oePo09zS8v2p6gb+lhdxfxa/eF6YhRWnI9DRkRhpSIqTedYxEayWP1J+ldKPZm5BFRZKEmxpyY1CSvMWLQ0F609w5v6g6v5BeJXY+b5L+Q3Gmn0OcYnzf9pw41XdFz1aUqNzYBPJGGnzhQJ0UDtR7quWSNQG/HAp7FlcXSjQ1ctNetc9TPVNyu91qARadi84x6qz6aBBTnBlpaWqU/U2ea3VJY6I1/qZI2DwNN40caUE2AOrcs+pD4bW+cJ2nRnLXt5CCtSypLpXOuWhEm2rZSvHF56bGYACLt7S/fITpbAWkTKkkzlrIsnMvpFq+Gc2+Fqq56VJxY1CW3FwZmxojMlRXiaRqc+DiujGxsxayYsBC9teef00Tu8rTWypJjSGy34fXQp7P2+DnwK9/W/tcouheID+HKAbvTJ89Vv+b2WfnLdOKUH2eWqo+fy1Vn7+Wqv8hLVWfh5aqz0tLy89TS8vPX0vLz7Xw/rAckaP19QV+QZKunbdU8nqqayRJ6L/0V5KbJT9e7hsRDCBJqgtJq5tCtb4mqQ5adkTyRVsFf6i5pSkgB+oKSspKpxszSf1b3xIoPrxOoNvnddHm5nUQhaOk/h1zxipJC5ZWVLrBb8zHq4tJydl3JvWSBQuq3TVSTcVcrxs5NEnUaQFyaaUgzb9hcUWlZ56Ae+0qpr9Ptbycv4py4Ptndbz0gkx/JEokF1I5nOdVrPoSGN5SnFZMw3uUNVwFZed0IzS5dTQ9ee5uUwMVDXBVs7YMRUUC047x/ajatOkVpAxjN4qS6021UNrVpLrHA15Iq5cm7WpXfS3335uano3JNcrpVWp65XFabvjKjYR3t0qpC6L/sQuhtSmTO2ENBEi/MFpXogFvDF8ikd+GSdFIoC79omhdCcKBQFoBBrrOWRud3mOrS2CAK8v1jd70VnIj8067r9fQTRhdOm7QkgyuFNZzGdxSrTcMEE/1iGl3dKfbG7naOR3mLh3Xp18XCUkN0NOC8uhdwoZtDr0dG0J9i5ej6/0Wu4NYby3ay7310qVfi60XsTYS4SwidTN8WmWc03XR5eXcXcfpl1wbepG0G6/TE9HeCm6UCrYjsxSkFhAdxvnSrYF1zPOZ3m+vc73kSmitxv0G7vgb3P2ucweBUL3exFA8UndaqUj//o/dv67Lk/y8NM2szvn6c4OuehbfVRN9rTFzASZXyxvVMXc3vU4V5L1Bo0vl003pW7g83aCzNJCO9Xppzk9zYzk8Y1eHk8KVYFNoChh0ONzd8gajHno7vEEhwNYqJbC7W8GLwWTBwLxb1vXXfFFx+g3s+rFIY1Cgvu5/AFj8a6spjQAA'
bin = gzip.decompress(base64.b64decode(gz))
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
with open(pymain, "wb") as f:
    f.write(bin)
os.chmod(pymain, stat.S_IRUSR | stat.S_IWUSR | stat.S_IXUSR)
if p == "":
    pymain = "./" + pymain
subprocess.call(pymain)


# compiled by pythran
'''
#pythran export main2()
n,m=[int(j) for j in input().split()]
dp=[10**18]*(2**(n))
dp[0]=0
cost=[]
for i in range(m):
    x,y=[int(j) for j in input().split()]
    tmp=set([int(j) for j in input().split()])
    ind=0
    for j in range(1,n+1):
        if j in tmp:
            ind|=2**(j-1)
    dp[ind]=x
    cost.append((ind,x))

for i in range(2**n):
    for j in range(m):
        dp[i|cost[j][0]]=min(dp[i|cost[j][0]],dp[i]+cost[j][1])

if dp[-1]!=10**18:
    print(dp[-1])
else:
    print(-1)

'''

Submission status: Accepted

Solution code:
def resolve():
    N,M = map(int,input().split())

    DP = [10 ** 8  + 1 for _ in range(1 << N)]
    DP[0] = 0

    for _ in range(M):
        a,_ = map(int,input().split())
        c = list(map(int,input().split()))
        bit = 0
        for j in c:
            bit |= 1 << (j-1)
        for j in range(1 << N):
            DP[j | bit] = min(DP[j]+a,DP[j|bit])
    print(DP[-1] if DP[-1] != 10 ** 8 + 1 else -1)
resolve()

Submission status: Accepted

Solution code:
n,m=[int(j) for j in input().split()]
dp=[10**18]*(2**(n))
dp[0]=0
cost=[]
for i in range(m):
    x,y=[int(j) for j in input().split()]
    tmp=set([int(j) for j in input().split()])
    ind=0
    for j in range(1,n+1):
        if j in tmp:
            ind|=2**(j-1)
    dp[ind]=x
    cost.append((ind,x))

for i in range(2**n):
    for j in range(m):
        dp[i|cost[j][0]]=min(dp[i|cost[j][0]],dp[i]+cost[j][1])

if dp[-1]!=10**18:
    print(dp[-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m=[int(j) for j in input().split()]
dp=[10**8]*(2**n)
dp[0]=0
cost=[]
for i in range(m):
    x,y=[int(j) for j in input().split()]
    tmp=[int(j) for j in input().split()]
    ind=0
    for j in tmp:
        ind|=1<<(j-1)
    cost.append((ind,x))

for i in range(1<<n):
    for j in range(m):
        dp[i|cost[j][0]]=min(dp[i|cost[j][0]],dp[i]+cost[j][1])

if dp[-1]!=10**8:
    print(dp[-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
keys=[None]*m
dp=[-1]*(2**n)
dp[0]=0
for i in range(m):
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  cond=0
  for j in c:
    cond+=2**(j-1)
  keys[i]=[a,cond]
for key in keys:
  for sta in range(2**n):
    if dp[sta]==-1:continue
    if dp[sta|key[1]]==-1:
      dp[sta|key[1]]=key[0]+dp[sta]
    else:
      dp[sta|key[1]]=min(dp[sta|key[1]],dp[sta]+key[0])
print(dp[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
keys=[None]*m
dp=[-1]*(2**n)
dp[0]=0
for i in range(m):
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  cond=0
  for j in c:
    cond+=2**(j-1)
  keys[i]=[a,cond]
for key in keys:
  for sta in range(2**n):
    if dp[sta]==-1:continue
    if dp[sta|key[1]]==-1:
      dp[sta|key[1]]=key[0]+dp[sta]
    else:
      dp[sta|key[1]]=min(dp[sta|key[1]],dp[sta]+key[0])
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
kagi=[[]for _ in range(m)]
for _ in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    kagi[_].append(a)
    kagi[_].append(c)

dp=[10**7 for _ in  range(2**n)]
dp[0]=0
for i in range(2**n):
    for j in range(m):
        l=kagi[j][1]
        ni=0
        for k in l:
            ni+=2**(k-1)
        dp[ni|i]=min(dp[ni|i],dp[i]+kagi[j][0])

if dp[-1]==10**7:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import sys


def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    a = [0] * m
    c = [0] * m
    inf = float('inf')

    for i in range(m):
        ai, bi = [int(s) for s in sys.stdin.readline().strip().split()]
        a[i] = ai
        ci = [int(s)-1 for s in sys.stdin.readline().strip().split()]
        # print(ci)
        c_val = sum([2 ** num for num in ci])
        c[i] = c_val

    dp = [[inf] * (2 ** n) for _ in range(m)]
    for i in range(m):
        dp[i][0] = 0

    for j in range(2 ** n):
        first_key_boxes = c[0]
        if first_key_boxes & j == j:
            dp[0][j] = a[0]

    for i in range(1, m):
        for j in range(1, 2 ** n):
            prev = j & (~c[i])
            dp[i][j] = min(dp[i-1][j], a[i] + dp[i-1][prev])
    if dp[m-1][2**n-1] == inf:
        print(-1)
    else:
        print(dp[m-1][2**n-1])


main()

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().split())

M = 1<<n
dp = [10**9]*M
dp[0] = 0
for i in xrange(m):
	a,b = map(int,raw_input().split())
	c = map(int,raw_input().split())
	mask = 0
	for x in c:
		mask += 1<<(x-1)
	for j in xrange(M):
		dp[j|mask] = min(dp[j|mask], dp[j]+a)
	#print dp
 
if dp[M-1] >= 10**9:
	print -1
else:
	print dp[M-1]

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    ABC = []
    c_all_or = 0
    where_open = lambda s: sum(2**j for j in s)
    for i in range(M):
        a, b = (int(j) for j in input().split())
        c = {int(j)-1 for j in input().split()}
        wc = where_open(c)
        c_all_or |= wc
        ABC.append((a,b,wc))
    if c_all_or != ((1<<N) - 1):
        print(-1)
        return 0
    r = [10**9] * (1<<N)
    r[0] = 0
    for bit in range(1,1<<N):
        q = r[bit]
        for i in range(M):
            cur = ABC[i][2]
            less = (bit ^ cur) & bit
            q = min(q,r[less] + ABC[i][0])
        r[bit] = q
    
    print(r[(1<<N) - 1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
f,*L=open(0).readlines()
n,m=map(int,f.split())
t=[(int(a.split()[0]),list(map(int,b.split()))) for a,b in zip(*[iter(L)]*2)]
K=[]
for a,C in t:
  r=0
  for c in C:
    r|=2**(c-1)
  K.append((a,r))
INF=float('inf')
dp=[INF]*(2**n)
dp[0]=0
for g in range(2**n):
  for a,c in K:
    if dp[g|c]>dp[g]+a:
      dp[g|c]=dp[g]+a
print(-1 if dp[-1]==INF else dp[-1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())

L={}
for i in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    d=0
    for j in c:
        d+=2**(N-j)
    if d not in L:
        L[d]=a
    else:
        if L[d]>a:
            L[d]=a
#print(L)

D={}
D[0]=0
C=0
for i in range(N):
    C+=2**(N-1-i)
    E={}
    for j in D:
        for k in L:
            if j>=C:
                if j not in E:
                    E[j]=D[j]
                else:
                    if E[j]>D[j]:
                        E[j]=D[j]
            if j|k>=C:
                if j|k not in E:
                    E[j|k]=D[j]+L[k]
                else:
                    if E[j|k]>D[j]+L[k]:
                        E[j|k]=D[j]+L[k]
    #print(E)
    D=E
if len(D)==0:
    print(-1)
else:
    print(D[2**N-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split(" "))
a = [0] * m
b = [0] * m
c = [[]] * m
INF = int(10e8)
dp = [INF] * (2 ** n)
dp[0] = 0
for i in range(m):
    a[i], b[i] = map(int, input().split(" "))
    c[i] = list(map(int, input().split(" ")))

for i in range(m):
    keyState = 0
    for j in c[i]:
        key = 1 << j - 1
        keyState = keyState | key
    for k in range(2**n):
        nextState = k | keyState
        dp[nextState] = min(dp[nextState], dp[k] + a[i])
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
#Get Everything
n,m=map(int,input().split())
ab=[]
c=[]
inf=float("inf")
for i in range(m):
    ab.append(list(map(int,input().split())))
    lst=list(map(int,input().split()))
    num=0
    for u in lst:
        num+=2**(u-1)
    c.append(num)
dp=[[inf]*(2**n) for _ in range(m+1)]
for i in range(m):
    dp[i][0]=0
for i in range(m):
    for j in range(2**n):
        if dp[i][j]!=inf:
            dp[i+1][j|c[i]]=min(dp[i+1][j|c[i]],dp[i][j]+ab[i][0])
            dp[i+1][j]=min(dp[i+1][j],dp[i][j])
if dp[m][2**n-1]!=inf:
    print(dp[m][2**n-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split(' '))
    dp = [10**9 for _ in range(2**n)]
    dp[0] = 0
    for i in range(m):
        a, b = map(int, input().split(' '))
        c = list(map(int, input().split(' ')))
        num = 0
        for j in range(b):
            num += 1 << (c[j]-1)
        for s in range(2**n):
            if dp[s|num] >= dp[s] + a:
                dp[s|num] = dp[s] + a
    if dp[-1] == 10**9:
        print(-1)
    else:
        print(dp[-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split(' '))
dp = [10**9 for _ in range(2**n)]
dp[0] = 0
for i in range(m):
    a, b = map(int, input().split(' '))
    c = list(map(int, input().split(' ')))
    num = 0
    for j in range(b):
        num += 1 << (c[j]-1)
    for s in range(2**n):
        if dp[s|num] >= dp[s] + a:
            dp[s|num] = dp[s] + a
if dp[-1] == 10**9:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  n, m = map(int, input().split())
  ps = [1e+9] * (2 ** n)
  ps[0] = 0

  for _ in range(m):
    p, _ = map(int, input().split())
    k = 0

    for i in map(int, input().split()):
      k |= 1 << (i - 1)

    for i in range(len(ps)):
      s = k | i
      ps[s] = min(ps[i] + p, ps[s])

  if ps[-1] == 1e+9:
    ps[-1] = -1

  print(ps[-1])


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
#input
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    C[i] = list(map(int, input().split()))

#output
dp = [9**9]* (1<<N)

def list_to_bin(my_list):
    my_bin = 0
    for l in my_list:
        my_bin += 1<<(l-1)
    return my_bin

for i in range(M):
    C[i] = list_to_bin(C[i])

dp[0] = 0
for i in range(M):
    for s in range(1<<N):
        dp[s|C[i]] = min(dp[s|C[i]], dp[s] + A[i])

if dp[-1] == 9**9:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from pprint import pprint
N, M = map(int, input().split())
A = [-1]*M
B = [-1]*M
C = [-1]*M

for i in range(M):
    A[i], B[i] = map(int, input().split())
    ls = list(map(int, input().split()))
    c = 0
    for j in range(len(ls)):
        c += 2 ** (ls[j]-1)
    C[i] = c


dp = [[float('inf')]*(2**N) for _ in range(M)]

j = 0
for i, di in enumerate(C):
    if i == 0:
        dp[i][di] = A[i]
        dp[i][0] = 0
        continue
    for j in range(2**N):
        stay = dp[i - 1][j | di]
        buy = dp[i - 1][j] + A[i]
        now = dp[i][j | di]
        dp[i][j | di] = min(stay, buy, now)
    for j in range(2**N):
        dp[i][j] = min(dp[i][j], dp[i-1][j])

ans = dp[-1][2**N-1]
if ans > sum(A):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:

def main():
  n,m=map(int,input().split())
  a=[0 for i in range(m)]
  b=[0 for i in range(m)]
  c=[[] for i in range(m)]
  for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(int,input().split()))
  
  dp=[float("inf") for i in range(2**n)]
  dp[0]=0
  for i in range(m):
    now=0
    for j in c[i]:
      jj=1<<j-1
      now=now|jj
    for k in range(2**n):
      kk=k|now
      dp[kk]=min(dp[kk],dp[k]+a[i])
    

  if dp[-1]==float("inf"):
    print(-1)
  else:
    print(dp[-1])
    
if __name__ == '__main__':  
  main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def main():
  n,m=map(int,input().split())
  a=[0 for i in range(m)]
  b=[0 for i in range(m)]
  c=[[] for i in range(m)]
  for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(int,input().split()))
  
  dp=[float("inf") for i in range(2**n)]
  dp[0]=0
  for i in range(m):
    now=0
    for j in c[i]:
      jj=1<<j-1
      now=now|jj
    for k in range(2**n):
      kk=k|now
      dp[kk]=min(dp[kk],dp[k]+a[i])
    

  if dp[-1]==float("inf"):
    print(-1)
  else:
    print(dp[-1])
    
if __name__ == '__main__':  
  main()

Submission status: Accepted

Solution code:
box_num, key_num = map(int, input().split())
dp_length = 2**box_num
dp = [float('inf')] * dp_length
dp[0] = 0
for _ in range(key_num):
    current_key_price, _ = map(int, input().split())
    c = 0
    effects = list(map(int, input().split()))
    for i in effects:
        e = 1 << (i - 1)
        c += e
    for x in range(dp_length):
        new_price = dp[x] + current_key_price
        dp_index = c | x
        if dp[dp_index] > new_price:
            dp[dp_index] = new_price
    # print(dp)
if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

inf = 10 ** 10

dp = [inf] * (1 << N)
dp[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (i - 1) for i in map(int, input().split())])

    for j in range(1 << N):
      dp[j | c] = min(dp[j] + a, dp[j | c])

res = dp[-1] if dp[-1] != inf else -1
print(res)