CF740B Alyona and flowers

小 Alyona 正在庆祝生日！她的妈妈有一排 $n$ 朵花。每朵花都有一个心情值，第 $i$ 朵花的心情值为 $a_{i}$。心情值可以是正数、零或负数。 我们将一个子数组定义为一段连续的花。妈妈提出一些子数组。Alyona 想从妈妈建议的这些子数组中选择若干个（可以不选也可以全选）。之后，每朵花会为女孩增加它的心情值乘以这朵花被选择的子数组包含的次数的分数，作为女孩的幸福值。 例如，假设妈妈有 $5$ 朵花，它们的心情值分别是 $1,-2,1,3,-4$。妈妈建议了如下子数组：$(1,-2)$，$(3,-4)$，$(1,3)$，$(1,-2,1,3)$。如果女孩选择第三个和第四个子数组，则有： - 第一朵花包含在其中一个被选中的子数组中，因此为女孩幸福值贡献 $1×1=1$； - 第二朵花只在其中一个被选中的子数组中，为 $(-2)×1=-2$； - 第三朵花在两个被选中的子数组中，为 $1×2=2$； - 第四朵花在两个被选中的子数组中，为 $3×2=6$； - 第五朵花没有在任何被选中的子数组中，为 $(-4)×0=0$。 因此，幸福值总和为 $1+(-2)+2+6+0=7$。Alyona 想要选择一些子数组，使得幸福值尽可能大。请帮助她。 Alyona 可以选择任意数量的子数组，包括 $0$ 或全部。

第一行包含两个整数 $n$ 和 $m$（$1\leq n,m\leq100$），分别表示花的数量和妈妈建议的子数组数量。 第二行包含 $n$ 个整数，分别表示每朵花的心情值 $a_{1},a_{2},...,a_{n}$（$-100\leq a_{i}\leq100$）。 接下来的 $m$ 行，每行包含两个整数 $l_{i}$ 和 $r_{i}$（$1\leq l_{i}\leq r_{i}\leq n$），表示妈妈建议的第 $i$ 个子数组 $a[l_{i}],...,a[r_{i}]$。 每个子数组可能出现多次。

输出一个整数，表示为 Alyona 增加的最大可能幸福值。

第一个样例就是题目描述中的场景。 第二个样例，Alyona 应选择所有的子数组。 第三个样例的答案为 $0$，因为 Alyona 可以一个子数组都不选。 由 ChatGPT 5 翻译