T426479 「YAC Round 5」河童科技世界 No.1！

 > 河童科技世界第一！！！

擅于机械操作的河城荷取是一个疯狂的科学家，有一天她尝试在幻想乡搭建一个通信线路。有了通信线路，那么他们的通讯就会变得畅通无阻了，比如某位经营着夜雀食堂的鸟脑袋资本家米斯蒂娅就可以通过通信线路打电话随意邀请（~~强迫~~）别人来她的餐厅消费。 通信线路的信号站选址是非常有讲究的。在幻想乡中，一共有 $n$ 个备选的信号站地址，第 $i$ 个地址搭建信号站所需要消耗的花费是 $a_i$ （$i = 1, 2, \ldots , n$）。 为了保证幻想乡居民通信的质量，信号站的选址需要满足 $m$ 个要求。第 $i$ 个要求为 $l_i, r_i$，表示第 $l_i$ 到 第 $r_i$ 个地址中（包含 $l_i$ 和 $r_i$）**至少要建造 $1$ 座信号站**。 河城荷取需要确定信号站的选址方案，使得在满足所有要求的前提下，建造信号站所需的 **总花费最小**。

**有多组测试数据。** 第一行输入一个整数 $T$ 表示测试数据组数。 对于每组测试数据： 第一行输入一个整数 $n$ 表示备选地址的总数。 第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$，其中 $a_i$ 表示第 $i$ 个地址建设信号站所需花费。 第三行输入一个整数 $m$表示需要满足的要求的总数。 接下来 $m$ 行，第 $i$ 行输入两个整数 $l_i$ 和 $r_i$，表示第 $l_i$ 到 第 $r_i$ 个地址之间（含两端）至少需要建设 $1$ 座信号站。

对于每组测试数据： 输出一行一个整数，表示满足所有要求情况下，建造信号站所需的最小总花费。

#### 样例解释 对于第一组样例数据，最优方案是在第 $2$ 个和第 $6$ 个地址建设信号站。总成本为 $2 + 9 = 11$。 对于第二组样例数据，最优方案是在第 $2$ 个和第 $5$ 个地址建设信号站。总成本为 $3 + 2 = 5$。 #### 数据范围与约定 $1 \le n \le 5 \times 10^5$，$1 \le a_i \le 10^9$，$1 \le m \le 5 \times 10^5$，$1 \le l_i \le r_i \le n$ 。 保证所有数据 $\sum_{i=1}^T n \le 5 \times 10^5$，$\sum_{i=1}^T m \le 5 \times 10^5$ 。 #### 注意 数据较多，建议使用比较高效的容器及输入方式。