Type: Default 1000ms 256MiB

easy版实验

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

莲子为了完善她的论文,决定研究一些物体的物理性质。由于工作实在是太多,她邀请你帮忙完成其中的一个小实验。//其实并不easy(~ ̄▽ ̄)~

题目描述

莲子有一个初始在数轴 00 点并向数轴正方向移动的小球。她在数轴的 11 到 nn 这 nn 个点上设置了装置,当小球经过点 ii 时,她可以花费 aia_i 的代价让其改变移动方向(从数轴正方向切换为负方向,或者相反)。

莲子有 mm 个需要满足的条件,第 ii 个条件形如“小球需要从点 xix_i 移动到点 yiy_i 至少一次”,其中 xix_i 大于 yiy_i。更详细的说,该条件即要求小球的移动路径形如 …→xi→…→yi→…\ldots \to x_i\to\ldots\to y_i\to\ldots。

莲子想要知道她至少要花费多少代价才能满足所有条件。

输入格式

第一行两个整数 n,mn,m。

第二行 nn 个正整数描述序列 aa。

接下来 mm 行中,第 ii 行依次给出两个正整数表示 xix_i 和 yiy_i。

输出格式

一行一个整数,表示莲子至少要花费多少代价才能满足所有条件。

输入输出样例 #1

输入 #1

3 1
1 2 3
2 1

输出 #1

2

输入输出样例 #2

输入 #2

5 3
5 2 3 4 5
2 1
3 2
3 1

输出 #2

3

说明/提示

样例解释

如图所示给出了两个样例的移动路线。数轴上方的是在每个点转向的代价,下方的是坐标。

样例 #1

莲子让小球在经过点 22 时反转方向恰好能满足所有条件,总花费代价为 22。

样例 #2

莲子让小球在经过点 33 时反转方向恰好能满足所有条件,总花费代价为 33。

数据范围

本题采用捆绑测试。

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n,m\le } & \bm{a_i\le} & \bm{x_i,y_i\le} & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline 1 & 10 & 10 & 100 & 10 & - &-\cr\hline 2 & 10 & 10^3 & 10^8 & 10^3 & -&1 \cr\hline 3 & 30 & 2\times 10^5 & 10^8 & 2\times 10^5 & -&1,2 \cr\hline \end{array}$$

对于所有数据满足:1≤n,m≤2×1051\le n,m\le 2\times 10^5,1≤ai≤1081\le a_i\le 10^8,1≤yi<xi≤n≤2×1051\le y_i< x_i \le n\le 2\times 10^5。

校赛新手热身(二)

Not Attended
Status
Done
Rule
XCPC
Problem
7
Start at
2026-11-9 22:30
End at
2026-11-16 4:30
Duration
150 hour(s)
Host
Partic.
90