题目描述

由于你成功地在 $ \text{1 s} $ 内算出了上一题的答案，英雄们很高兴并邀请你加入了他们的游戏。然而进入游戏之后你才发现，英雄们打的游戏和你想象的并不一样……

英雄们打的游戏是这样的：首先系统会产生（注意不一定是随机产生）一个字符串，然后每个英雄就会开始根据自己分到的任务计算这个字符串的某些特征，谁先算出自己的答案谁就是胜者。

由于打游戏的英雄比较多，因此英雄们分到的任务也就可能很奇怪。比如你分到的这个任务就是这样：

定义这个字符串以第 $ i $ 个字符开头的后缀为后缀 $ i $ （编号从 $ 1 $ 开始），每个后缀 $ i $ 都有一个权值 $ w_i $ ，同时定义两个后缀 $ i,j $ ($ i\ne j $) 的贡献为它们的最长公共前缀长度加上它们权值的异或和，也就是 $ \mathrm{LCP}(i,j)+(w_i \mathbin{\text{xor}} w_j) $ 。而你的任务就是，求出这个字符串的所有后缀两两之间贡献的最大值。

输入格式

第一行一个正整数 $ n $，表示字符串的长度。
第二行一个仅包含小写英文字母的字符串，即系统产生的字符串。
第三行 $ n $ 个非负整数 $ w_i $，分别表示后缀 $ 1 $ ~ $ n $ 的权值。

输出格式

一行一个整数表示答案。

样例

input

7
acbabac
0 1 5 6 4 2 3

output

7

后缀 $ 1 $ 和后缀 $ 4 $ 的贡献是 $ 1+(0\;\text{xor}\;6)=7 $ ，不难验证它们的贡献确实是所有可能的贡献中最大的。

数据范围与提示

对于 $ 30\% $ 的数据，$ n\le 5\times 10^3 $；
对于另 $ 30\% $ 的数据，保证字符串是随机生成的；
对于另 $ 10\% $ 的数据，$ w_i=0 $；
对于另 $ 10\% $ 的数据，$ w_i\le 1 $；
对于 $ 100\% $ 的数据，$ n\le 10^5 $，$ w_i< n $ 。

题解&标程