题目描述

"不要因为贪恋旧的而不去尝试新的,你是祂的子民,你当充满勇气。"

"不要因为怀恋家乡而不去探寻新的土地,无论你身在何处,祂都与你同在。"

"不要因为已经拥有财富而不去冒险,你本可以拥有更庞大的财富。"

"因为,祂是包容的,祂所守护的这片土地理当是包容的,祂的子民,更应是包容的。 "


秉承着包容精神,Elo的子民XHM从炎国给Elo带来了他虔诚的贡品:一串"如意",

"如意"这个东西,有黑色,白色两种类型,每个"如意"还有一个能量值$b$,

"如意"间可以两两配对,配对后的"如意"就会立马爆炸,然后消失。具体的,如果串中第$x$个"如意"和第$y$个"如意"进行配对(要保证$x<y$),产生的爆炸会释放出$b_y-b_x$点能量。

幸运的是,Elo祂并不怕爆炸,祂只是觉得,在谢拉格这片白色的土地上,理不应该存在黑色的如意,因此祂想通过配对的方式消除掉所有的黑色"如意",

同时祂又不想造成过大的影响,因此祂想知道,在消除所有黑色"如意"的前提下,产生的爆炸能量总和最小能是多少?


输入格式

第一行一个正整数$n\ (1\leq n \leq 5000)$,表示有多少个"如意",

第二行给出一个长度为$n$的01串,$0$表示当前的如意是白色的,$1$表示当前的如意是黑色的,

第三行$n$个正整数,第$i$个正整数$b_i\ (1\leq b_i \leq 10^9)$,表示第$i$个如意的值。


输出格式

一行一个整数,表示爆炸能量总和的最小值。保证黑色“如意”可以全部消除


样例数据

输入

样例一
4
1100
1 30 3 40


样例二
4
0000
10 20 3 4

输出

样例一
12

样例二
-23

备注


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 512MB
评测模式: Normal

题解