M 国要在 A 城市与 B 城市之间建设 5G 基站，已知 A 城市与 B 城市的距离为 nn 千米，工程师们已经考察在从 A 城市往 B 城市方向上 1，2，...，n 千米处建设 5G 基站的成本，分别是 w1w1​，w2w2​，...，wnwn​。 为了保证通信质量，5G 基站的选址还需要满足 mm 条需求，其中第 ii 条需求可以用 lili​ 和 riri​ 表示 (1≤li≤ri≤n1≤li​≤ri​≤n)，代表从 A 城市往 B 城市方向上 lili​ 千米到 riri​ 千米的位置之间（含两端）至少需要建设 1 座 5G 基站。 作为总工程师，您需要决定 5G 基站的数量与位置，并计算满足所有需求的最小总成本。 输入格式 第一行输入两个整数 nn 和 mm 分别表示距离和需求数量。 接下来一行输入 nn 个整数 w1w1​，w2w2​，...，wnwn​ 分别表示从 A 城市往 B 城市方向上 1，2，...，nn 千米处建设 5G 基站的成本。 接下来 mm 行，第 i 行输入两个整数 lili​ 和 riri​(1≤li≤ri≤n1≤li​≤ri​≤n) 表示从 A 城市往 B 城市方向上 lili​ 千米到 riri​ 千米的位置之间（含两端）至少需要建设 1 座 5G 基站。 输出格式 输出一行一个整数，表示满足所有需求的最小总成本。 用c++ 且1≤n≤106，1≤m≤1061≤m≤106，1≤wi≤1091≤wi​≤109，1≤li≤ri≤n1≤li​≤ri​≤n。要在1s内完成内存不超过128MB

这道题目可以使用线段树来解决。我们可以将需要建立基站的区间视为线段树中的叶子节点，然后通过不断地合并区间来得到满足所有需求的最小总成本。具体来说，我们可以在线段树中每个节点维护该节点所覆盖的区间中的最小建站成本和该区间中至少需要建立的基站数量。在合并两个区间时，我们可以使用类似于归并排序的方法，将两个区间合并成一个区间，并更新该区间中的最小建站成本和至少需要建立的基站数量。最后，根节点中的最小建站成本即为满足所有需求的最小总成本。

具体的实现细节可以参考下面的代码：