{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e Alice and Bob are playing \"Gems Fight!\":\u003cbr\u003e There are Gems of G different colors , packed in B bags. Each bag has several Gems. G different colors are numbered from color 1 to color G.\u003cbr\u003e Alice and Bob take turns to pick one bag and collect all the Gems inside. A bag cannot be picked twice. The Gems collected are stored in a shared cooker.\u003cbr\u003e After a player ,we name it as X, put Gems into the cooker, if there are S Gems which are the same color in the cooker, they will be melted into one Magic Stone. This reaction will go on and more than one Magic Stone may be produced, until no S Gems of the same color remained in that cooker. Then X owns those new Magic Stones. When X gets one or more new Magic Stones, he/she will also get a bonus turn. If X gets Magic Stone in a bonus turn, he will get another bonus turn. In short,a player may get multiple bonus turns continuously.\u003cbr\u003e There will be B turns in total. The goal of \"Gems Fight!\" is to get as more Magic Stones than the opponent as possible.\u003cbr\u003e Now Alice gets the first turn, and she wants to know, if \u003cb\u003eboth of them act the optimal way\u003c/b\u003e, what will be the difference between the number of her Magic Stones and the number of Bob\u0027s Magic Stones at the end of the game.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" There are several cases(\u0026lt;\u003d20).\u003cbr\u003e In each case, there are three integers at the first line: G, B, and S. Their meanings are mentioned above.\u003cbr\u003e Then B lines follow. Each line describes a bag in the following format:\u003cbr\u003e \u003cbr\u003e n c\u003csub\u003e1\u003c/sub\u003e c\u003csub\u003e2\u003c/sub\u003e ... c\u003csub\u003en\u003c/sub\u003e\u003cbr\u003e \u003cbr\u003e It means that there are n Gems in the bag and their colors are color c\u003csub\u003e1\u003c/sub\u003e,color c\u003csub\u003e2\u003c/sub\u003e...and color c\u003csub\u003en\u003c/sub\u003e respectively.\u003cbr\u003e 0\u0026lt;\u003dB\u0026lt;\u003d21, 0\u0026lt;\u003dG\u0026lt;\u003d8, 0\u0026lt;n\u0026lt;\u003d10, S \u0026lt; 20.\u003cbr\u003e There may be extra blank lines between cases. You can get more information from the sample input.\u003cbr\u003e The input ends with G \u003d 0, B \u003d 0 and S \u003d 0."}},{"title":"Output","value":{"format":"HTML","content":" One line for each case: the amount of Alice\u0027s Magic stones minus the amount of Bob\u0027s Magic Stones."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 4 3\r\n2 2 3\r\n2 1 3\r\n2 1 2\r\n3 2 3 1\r\n\r\n3 2 2\r\n3 2 3 1\r\n3 1 2 3\r\n\r\n0 0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n-3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e For the first case, in turn 2, bob has to choose at least one bag, so that Alice will make a Magic Stone at the end of turn 3, thus get turn 4 and get all the three Magic Stones.\u003cbr\u003e"}}]}