该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 C 手上有 $n$ 张扑克牌，按照 $1,2,\cdots,n$ 的顺序排列。一开始，有些牌是正面朝上的，有些牌则是背面朝上的，而小 C 希望所有的牌都能调整为正面朝上。

这些牌有一种奇怪的特性，当小 C 翻转第 $i$ 张牌时，牌 $i+1,i+2,\cdots,r_i$ 也会在同一时刻翻转（当 $r_i=i$ 时，没有额外的牌被翻转），而其他的牌保持不变。此外，小 C 翻转第 $i$ 张牌需要 $t_i$ 的时间。

小 C 想知道最少多少时间后，所有的牌都能变为正面朝上。

输入格式

• 第一行包含一个整数 $n$，表示扑克牌的张数。
• 第二行包含一个长度为 $n$ 的字符串 $s_1s_2\cdots s_n$，当 $s_i$ 为 0 时表示正面朝上，而 $s_i$ 为 1 时表示背面朝上。
• 第三行包含一个长度为 $n$ 的数组 $r_1,r_2,\cdots,r_n$，其中 $r_i$ 表示翻转牌 $i$ 时，影响到的最右侧牌。
• 第四行包含一个长度为 $n$ 的数组 $t_1,t_2,\cdots,t_n$，其中 $t_i$ 表示翻转牌 $i$ 所需的时间。

输出格式

• 输出一个整数，表示小 C 所需的最小时间。

样例输入

9
110101011
4 3 8 5 8 6 9 8 9
1 2 3 4 5 6 7 8 9

样例输出

23

数据范围

对于全部测试数据，$1\le n\le 10^6,\,i\le r_i\le n,\,1\le t_i\le 10^9,$ $s$ 为长度 $n$ 的 01 串，其中

• 对于 $20\%$ 的测试数据，满足 $n\le 20$；
• 对于 $40\%$ 的测试数据，满足 $n\le 300$；
• 对于 $60\%$ 的测试数据，满足 $n\le 5000$；
• 对于 $80\%$ 的测试数据，满足 $n\le 10^5$。