配点 : $300$ 点

問題文

子供と大人があわせて $N$ 人います。$i$ 番目の人の体重は $W_i$ です。 それぞれの人が子供か大人かは、0 と 1 からなる長さ $N$ の文字列 $S$ によって表され、 $S$ の $i$ 文字目が 0 であるとき $i$ 番目の人が子供であることを、1 であるとき $i$ 番目の人が大人であることをさします。

ロボットである高橋君に対して実数 $X$ を設定すると、 高橋君はそれぞれの人に対して、体重が $X$ 未満なら子供、$X$ 以上なら大人と判定します。 実数 $X$ に対して$f(X)$ を、高橋君に $X$ を設定したときに $N$ 人のうち子供か大人かを正しく判定できる人数で定めます。

$X$ が実数全体を動くとき、$f(X)$ の最大値を求めてください。

制約

• $1\leq N\leq 2\times 10^5$
• $S$ は 0 と 1 からなる長さ $N$ の文字列
• $1\leq W_i\leq 10^9$
• $N,W_i$ は整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$S$

$W_1$ $W_2$ $\ldots$ $W_N$

出力

$f(X)$ の最大値を整数で一行に出力せよ。

5
10101
60 45 30 40 80

4

$X=50$ と設定すると、高橋君は $2,3,4$ 番目の人を子供、 $1,5$ 番目の人を大人と判定します。 実際には $2,4$ 番目の人が子供、 $1,3,5$ 番目の人が大人であるので、このとき、$1,2,4,5$ 番目の合計 $4$ 人に対して正しく判定できています。 よって、$f(50)=4$ です。

$5$ 人全員に対して正しく判定できるような $X$ は存在しないのでこのときが最大です。よって、$4$ を出力します。

3
000
1 2 3

3

例えば、$X=10$ とすると最大値 $f(10)=3$ を達成します。 全員が大人、または全員が子供である可能性もあることに注意してください。

5
10101
60 50 50 50 60

4

例えば、$X=55$ とすると最大値 $f(55)=4$ を達成します。 同じ体重の人が複数人存在する可能性もあることに注意してください。