题目内容

在一款古老的消除游戏中，有 $n$ 个宝石排成一行，宝石只有两种类型，且任意相邻两颗宝石的类型都不相同。宝石依次编号为 $1$ 到 $n$。

在两颗相邻宝石 $i$ 和 $i+1$ 之间，存在一个隐藏的奖励数值 $b_i$ ($1 \le i \le n-1$)。当你选择一对相邻宝石并消除它们时，你将获得对应的奖励 $b_i$。消除后，剩余的宝石保持原有相对顺序重新拼接在一起。由于任意相邻宝石类型都不同，因此每次选择任意一对相邻宝石都是合法的。

奖励数组 $b$ 的长度固定为 $n-1$，且不会因为消除操作而改变。也就是说，即使在消除操作之后，当你选择当前序列中第 $i$ 颗和第 $i+1$ 颗宝石时，你获得的奖励依然是初始数组中 $b_i$ 的值（奖励值与其在原始序列中的位置绑定，直到该位置不再存在）。

你可以不断进行消除操作，直到无法继续（剩余宝石数量不超过 $1$）。设你总共进行了 $m$ 次消除，获得的奖励之和为 $S$。现在，请你分别求出在所有可行的消除方案中，$S$ 可能取得的最大值以及最小值。

数据范围与约束