問題一覧 > 通常問題

No.1912 Get together 2

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 49
作問者 : chineristAC / テスター : tokusakurai shotoyoo
お気に入りにしたユーザー ProblemId : 6852 / 自分の提出
問題文最終更新日: 2022-04-05 18:11:18
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 340 (順位表) の他の問題:

Problem Statement

There are $N$ slimes and $M$ boxes. The value of slime $i\ (1\le i \le N)$ is $V_i$. The slimes and boxes are numbered, and they are denoted as slime $i\ (1 \le i \le N)$ and box $j\ (1\le j \le M)$, respectively.

You will now put each of the $N$ slimes into exactly $1$ of the $M$ boxes (there may be boxes that do not contain even $1$ slime). There is a compatibility between slimes and boxes, represented by a string $S_i$ of length $M$ consisting only of o and x. If the $j$-th character of $S_i$ is o, slime $i$ can be put into box $j$; if it is x, it cannot.

Find the maximum possible value of $\displaystyle \sum_{j=1}^{M}($the sum of the values of the slimes in box $j$$)^2$.

Input

$N$ $M$
$V_1$ $V_2$ $\dots$ $V_N$
$S_1$
$S_2$
$\vdots$
$S_N$
  • $1 \le N \le 10^5$
  • $1 \le M \le 20$
  • $1 \le V_i \le 10^4$
  • $|S_i|=M$
  • $S_i$ contains at least $1$ o
  • All values in the input (except $S_i$) are integers

Output

Print the answer.

End the output with a newline.

Sample

Sample 1
Input
3 3
3 4 5
ooo
oox
xox
Output
144

It is optimal to put all the slimes into box $2$.

Sample 2
Input
4 2
2 3 6 5
ox
xo
oo
xo
Output
200

Only slime $3$ has a choice of box. In this case, putting it into box $2$ together with slimes $2,\ 4$ makes the above value $2^2+(3+6+5)^2=200$, which is optimal.

Sample 3
Input
13 6
404 386 221 993 1 708 468 832 20 879 704 589 311
xoxxxx
xooxox
oxxoxx
xoooox
ooxoox
oxooxo
xxxxoo
xooxox
ooooox
xxooxo
xxooxx
xxoxox
oxxxoo
Output
26942778

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。