AT_s8pc_5_f Lunch Menu

AtCoder 咖啡馆有 $N$ 个餐食，编号从 $1$ 到 $N$。第 $i$ 个餐食（$1 \leq i \leq N$）的美味度为 $a_i$。 square1001 君将在 AtCoder 咖啡馆用餐 $Q$ 天。第 $i$ 天（$1 \leq i \leq Q$），他会从编号在 $l_i$ 到 $r_i$ 之间的餐食中，选择美味度最大的那一道。如果在该区间内没有可选的餐食，他就会空腹回家。 你是恶魔，可以用魔力将 $N$ 个餐食中的 $M$ 个从菜单上抹去，使其无法被选择。你的目标是让 square1001 君所选餐食的美味度总和尽可能小。 请你求出 square1001 君所选餐食美味度总和的最小值。

输入按以下格式从标准输入读入。 > $N$ $M$ $Q$ > $a_1\ a_2\ a_3\ \cdots\ a_N$ > $l_1\ r_1$ > $l_2\ r_2$ > $l_3\ r_3$ > : > : > $l_Q\ r_Q$

请输出 square1001 君所选餐食美味度总和的最小值。

## 限制条件 - $N$ 是 $1$ 到 $50$ 之间的整数。 - $M$ 是 $0$ 到 $N$ 之间的整数。 - $Q$ 是 $1$ 到 $50$ 之间的整数。 - $a_i\ (1 \leq i \leq N)$ 是 $1$ 到 $1\,000\,000\,000$ 之间的整数。 - $l_i, r_i$ 满足 $1 \leq l_i \leq r_i \leq N$。 ## 子任务 子任务 $1$ [$60$ 分] - $N \leq 15$。 - $Q = 1$。 子任务 $2$ [$60$ 分] - $N \leq 15$。 子任务 $3$ [$250$ 分] - 对所有 $i\ (1 \leq i \leq N)$，都有 $a_i = 1$。 子任务 $4$ [$630$ 分] - 无额外限制。 ## 样例解释 1 如果你将编号为 $2$ 和 $3$ 的餐食抹去，每一天美味度的最大值分别为 $4$、$3$、$8$、$4$、$8$，总和为 $27$。 由 ChatGPT 4.1 翻译