{"raw_statement":[{"iden":"problem statement","content":"The programming contest World Tour Finals is underway, where $N$ players are participating, and half of the competition time has passed. There are $M$ problems in this contest, and the score $A_i$ of problem $i$ is a multiple of $100$ between $500$ and $2500$, inclusive.\nFor each $i = 1, \\ldots, N$, you are given a string $S_i$ that indicates which problems player $i$ has already solved. $S_i$ is a string of length $M$ consisting of `o` and `x`, where the $j$\\-th character of $S_i$ is `o` if player $i$ has already solved problem $j$, and `x` if they have not yet solved it. Here, none of the players have solved all the problems yet.\nThe total score of player $i$ is calculated as the sum of the scores of the problems they have solved, plus a **bonus score** of $i$ points.  \nFor each $i = 1, \\ldots, N$, answer the following question.\n\n*   At least how many of the problems that player $i$ has not yet solved must player $i$ solve to exceed all other players' current total scores?\n\nNote that under the conditions in this statement and the constraints, it can be proved that player $i$ can exceed all other players' current total scores by solving all the problems, so the answer is always defined."},{"iden":"constraints","content":"*   $2\\leq N\\leq 100$\n*   $1\\leq M\\leq 100$\n*   $500\\leq A_i\\leq 2500$\n*   $A_i$ is a multiple of $100$.\n*   $S_i$ is a string of length $M$ consisting of `o` and `x`.\n*   $S_i$ contains at least one `x`.\n*   All numeric values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $\\ldots$ $A_M$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$"},{"iden":"sample input 1","content":"3 4\n1000 500 700 2000\nxxxo\nooxx\noxox"},{"iden":"sample output 1","content":"0\n1\n1\n\nThe players' total scores at the halfway point of the competition time are $2001$ points for player $1$, $1502$ points for player $2$, and $1703$ points for player $3$.\nPlayer $1$ is already ahead of all other players' total scores without solving any more problems.\nPlayer $2$ can, for example, solve problem $4$ to have a total score of $3502$ points, which would exceed all other players' total scores.\nPlayer $3$ can also, for example, solve problem $4$ to have a total score of $3703$ points, which would exceed all other players' total scores."},{"iden":"sample input 2","content":"5 5\n1000 1500 2000 2000 2500\nxxxxx\noxxxx\nxxxxx\noxxxx\noxxxx"},{"iden":"sample output 2","content":"1\n1\n1\n1\n0"},{"iden":"sample input 3","content":"7 8\n500 500 500 500 500 500 500 500\nxxxxxxxx\noxxxxxxx\nooxxxxxx\noooxxxxx\nooooxxxx\noooooxxx\nooooooxx"},{"iden":"sample output 3","content":"7\n6\n5\n4\n3\n2\n0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}