机器人高桥

题目描述

有 $N$ 个人，每个人要么是小孩要么是大人。第 $i$ 个人的体重为 $W_i$。

每个人是小孩还是大人由长度为 $N$、由 0 和 1 组成的字符串 $S$ 指定。

若 $S$ 的第 $i$ 个字符为 0，则第 $i$ 个人是小孩；若为 1，则是大人。

当机器人高桥君被给定一个实数 $X$ 时， 高桥君把体重小于 $X$ 的人判定为小孩，把体重大于等于 $X$ 的人判定为大人。

对实数 $X$，令 $f(X)$ 为高桥君正确判定其小孩/大人身份的人数。

求所有实数 $X$ 中 $f(X)$ 的最大值。

输入格式

输入按以下格式从标准输入给出：

N
S
W_1 W_2 … 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 个人被正确判定。 于是 $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$。

注意，可能存在体重相同的多个人。

数据范围

• $1 \le N \le 2 \times 10^5$
• $S$ 是长度为 $N$、由 0 和 1 组成的字符串。
• $1 \le W_i \le 10^9$
• $N$ 和 $W_i$ 是整数。