103232: [Atcoder]ABC323 C - World Tour Finals

Problem Statement

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.

For 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.

The 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.
For each $i = 1, \ldots, N$, answer the following question.

• 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?

Note 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.

Constraints

• $2\leq N\leq 100$
• $1\leq M\leq 100$
• $500\leq A_i\leq 2500$
• $A_i$ is a multiple of $100$.
• $S_i$ is a string of length $M$ consisting of o and x.
• $S_i$ contains at least one x.
• All numeric values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_M$
$S_1$
$S_2$
$\vdots$
$S_N$

Output

Print $N$ lines. The $i$-th line should contain the answer to the question for player $i$.

Sample Input 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

Sample Output 1

0
1
1

The 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$.

Player $1$ is already ahead of all other players' total scores without solving any more problems.

Player $2$ can, for example, solve problem $4$ to have a total score of $3502$ points, which would exceed all other players' total scores.

Player $3$ can also, for example, solve problem $4$ to have a total score of $3703$ points, which would exceed all other players' total scores.

Sample Input 2

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

Sample Output 2

1
1
1
1
0

Sample Input 3

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

Sample Output 3

7
6
5
4
3
2
0

问题描述

编程竞赛World Tour Finals正在进行中，有N名选手参加，比赛时间已经过去了一半。 这次比赛有M道题目，每道题目的分数$A_i$在500到2500之间，包括500和2500，且为100的倍数。

对于每个$i = 1, \ldots, N$，你将得到一个字符串$S_i$，表示选手$i$已经解决的题目。$S_i$是一个长度为$M$的字符串，由o和x组成，其中$S_i$的第$j$个字符为o，表示选手$i$已经解决了问题$j$；如果选手$i$尚未解决该问题，则为x。请注意，目前没有任何选手解决完所有问题。

选手$i$的总分为他们已经解决的问题的分数之和，再加上一个附加分，即$i$分。
对于每个$i = 1, \ldots, N$，回答以下问题。

• 选手$i$必须解决至少多少个尚未解决的问题，才能超过其他选手当前的总分？

需要注意的是，在本问题的描述和约束条件下，可以证明选手$i$通过解决所有问题就可以超过其他选手当前的总分，因此答案始终是定义的。

约束条件

• $2\leq N\leq 100$
• $1\leq M\leq 100$
• $500\leq A_i\leq 2500$
• $A_i$是100的倍数。
• $S_i$是一个长度为$M$的字符串，由o和x组成。
• $S_i$至少包含一个x。
• 输入中的所有数值都是整数。

输入

输入从标准输入中给出，格式如下：

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出

打印$N$行。第$i$行应包含选手$i$的答案。

样例输入1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

样例输出1

0
1
1

在比赛时间的一半时，选手$1$的总分为$2001$分，选手$2$的总分为$1502$分，选手$3$的总分为$1703$分。

选手$1$无需再解决任何问题就可以领先其他选手的总分。

选手$2$可以，例如，解决问题$4$，总分为$3502$分，这将超过其他选手的总分。

选手$3$也可以，例如，解决问题$4$，总分为$3703$分，这将超过其他选手的总分。

样例输入2

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

样例输出2

1
1
1
1
0

样例输入3

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

样例输出3

7
6
5
4
3
2
0