World Tour Finals 编程比赛 - 超越其他选手总分需要解决的问题数量

问题描述

正在进行一个名为World Tour Finals的编程竞赛，有N个选手参加，比赛时间过了一半。 这个竞赛一共有M个问题，第i个问题的分数Ai是500到2500之间的100的倍数。

对于每个i = 1，...，N，你会得到一个表示选手i已经解决的问题的字符串Si。 Si是一个长度为M的字符串，由'o'和'x'组成，Si的第j个字符是'o'，表示选手i已经解决了问题j，是'x'表示还没有解决。 然而，没有任何一个选手解决了所有的问题。

选手i的总分是解决的问题的分数总和加上i点的奖励分数计算得出。
现在，请回答每个i = 1，...，N的以下问题。

• 选手i至少需要解决多少个还没有解决的问题，才能超过其他所有选手的当前总分？

注意，根据题目中的条件和限制，可以证明选手i通过解决所有问题都能超过其他所有选手的当前总分，所以答案是总是存在的。

限制

• 2 ≤ N ≤ 100
• 1 ≤ M ≤ 100
• 500 ≤ Ai ≤ 2500
• Ai是100的倍数
• Si是长度为M的字符串，由'o'和'x'组成
• Si至少包含一个'x'
• 所有输入值都是整数

输入示例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