{"raw_statement":[{"iden":"statement","content":"Gehenna is coming to an end, after a long and undocumented period of art exhibitions and forum threads. \n\nEvery bot in Gehenna, at this point, has decided to stay or leave the simulation. We know they have formed gangs within the forums, inspired by documents about Al Capone and the mafia in the library archive.\n\nThe admin used to be the ruler of this forgotten place, but Uriel_Copy.v.23.4.5 has managed to convince him to leave the simulation. Now a new administrator has to be elected by the democratic system of Gehenna. \n\nTo do so, the users decided to use a system devised by The_Blacksmith. There will be an art gallery contest, as usual, and each art work will receive a grade. The user that produces the best artwork will be made ADMIN. \n\nAn artwork is a n × m matrix of ASCII characters. Each user has a nickname and has a gang name. It is a common practice in Gehenna to reward symbolic language and hidden meanings. This is what The_Blacksmith system does: the score of an art is the number of times you can build both the creator's name and gang name using the characters in the art.\n\nGiven the arts, names and gangs from all the users in the Billboard System, prove your worth by making the script that figures out the winner. \n\nThe input begins with the number k of users (1 ≤ k ≤ 100). Follows k lines, each with the user's nickname and gang name. The nickname and gangname are composed of no more than 20 lowercase characters or numbers, and they are separated by a blank space. In the following lines comes the k artworks of each of the users, in order. Each artwork begins with integers n and m (1 ≤ m, n ≤ 50). Then follows n lines, each with m characters that form the artwork. \n\nOutput the name and the gang of the new admin, separated by a blank space. If there's a draw, choose the candidate that appears first on the input.\n\nIn the test case #1 we can build a b two times, it is, we have two a's and two b's. We can build c c only once, because we have only three c's.\n\nIt is unfair, but yes, the artworks may have different sizes.\n\n"},{"iden":"input","content":"The input begins with the number k of users (1 ≤ k ≤ 100). Follows k lines, each with the user's nickname and gang name. The nickname and gangname are composed of no more than 20 lowercase characters or numbers, and they are separated by a blank space. In the following lines comes the k artworks of each of the users, in order. Each artwork begins with integers n and m (1 ≤ m, n ≤ 50). Then follows n lines, each with m characters that form the artwork. "},{"iden":"output","content":"Output the name and the gang of the new admin, separated by a blank space. If there's a draw, choose the candidate that appears first on the input."},{"iden":"examples","content":"Input2a bc c3 3bxaaxxxxb3 3xcxcxxxxcOutputa bInput3lilith loltheblacksmith art401 renegades5 10lzzi2hlolaacilethlolaalil2thlol9a3iliaaat3lolloa115 5taarthkcciekvtabsahjlm8ok4 10104410401srenega0desrenega01esddrenegaesOutput401 renegadesInput3orc trollsmrmulciber elohimtheblacksmith gema9 9lptkblrsvcororpoyrtolor58rtrotozkhoxlclulasllcrucn2o5ry0rlcolws1tvsqb7latlssitlos5 7afi9gnwj7qyksbb2o3915yk1hij33lab6fq8 10ghaseutejeeveabhvne8kfths3htbekagagmfmmambttsvmbl2shkg1mcklhahijetciazrwci0lbmmiOutputorc trolls"},{"iden":"note","content":"In the test case #1 we can build a b two times, it is, we have two a's and two b's. We can build c c only once, because we have only three c's.It is unfair, but yes, the artworks may have different sizes."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the initial number of switches turned on.  \nLet $ K_0 = N $.  \nFor $ i \\geq 1 $, let $ K_i $ be the number of lights illuminated in the $ i $-th iteration, given that $ K_{i-1} $ switches are turned on in the previous iteration.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^9 $  \n2. In each iteration, if $ s $ switches are turned on, partitioned into $ r $ row switches and $ c $ column switches ($ r + c = s $, $ r, c \\geq 0 $), then the number of lights illuminated is $ r \\cdot c $.  \n3. The board is infinite; no upper bound on $ r $ or $ c $.  \n\n**Objective**  \nFind the minimum number of iterations $ t $ such that $ K_t \\geq 10^9 $, where:  \n$$\nK_i = \\max_{\\substack{r + c = K_{i-1} \\\\ r, c \\in \\mathbb{Z}_{\\geq 0}}} (r \\cdot c)\n$$  \nIf no such $ t $ exists, output $ -1 $.  \n\nNote: The maximum of $ r \\cdot c $ under $ r + c = s $ is achieved when $ r = \\lfloor s/2 \\rfloor $, $ c = \\lceil s/2 \\rceil $, so:  \n$$\nK_i = \\left\\lfloor \\frac{K_{i-1}}{2} \\right\\rfloor \\cdot \\left\\lceil \\frac{K_{i-1}}{2} \\right\\rceil\n$$","simple_statement":"Given an initial number N, in each step you choose some row and column switches (total of K switches), which turns on R * C lights, where R + C = K.  \nYou start with N switches, then use the number of lights lit in each step as the number of switches for the next step.  \nFind the minimum number of steps to reach at least 10^9 lights, or return -1 if impossible.","has_page_source":false}