翻转卡牌plus

文件与限制

输入文件：cardp.in；输出文件：cardp.out。

时间限制：1 秒；空间限制：512 MiB。使用 C++14 O2。

题目描述

大家都做过一道题——翻转卡牌

一开始有 $n$ 张卡牌放在桌上，有的朝上有的朝下

现在允许你将其中的一张翻转，并将它和它左右两侧的牌一起翻转，问最小的翻转次数

张老师已经 $AC$ 了这道题，但是聪明的他立刻就想到了一个加强版翻转卡牌

如果现在翻转卡牌不仅仅只影响相邻的卡牌呢？如果翻转不同卡牌时的消耗不同呢？

于是张老师设定了两个数值 $a_i$ 和 $b_i$，表示翻转第 $i$ 张卡牌时，会同时翻转 $i \sim a_i$ 编号的所有卡牌（保证 $i \leq a_i$），并且翻转这张卡牌会有 $b_i$ 点花费

现在张老师想知道，最少需要多少点花费才可以让现在的 $n$ 张卡牌全部正面朝上？

输入格式

输入第一行包含一个整数 $n$ 表示卡牌数量

输入第二行包含一个长度为 $n$ 的 $01$ 串，其中 $0$ 表示这张牌正面朝上，$1$ 表示这张牌反面朝上

接下来 $n$ 行，每行两个整数 $a_i,b_i$ 表示翻转第 $i$ 张牌的信息

输出格式

输出一个整数表示最小花费

数据范围

特别的，对于所有测试数据满足：$i \leq a_i \leq n, 1 \leq b_i \leq 10^9$

样例输入1

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

样例输出1

23

对于全部数据，$1\le n\le10^6$。