P11035 【MX-X3-T2】「RiOI-4」消えた夏の夢

原题链接：。 --- > いつまでも二人語り合おう\ 終わった夏を \ 探してた夢をそっと\ 終わらせよう戻らないように\ お別れだね\ 君へ届けと願った声が\ 風になって心の隙間を\ 通り抜けた\ ——《消えた夏の夢》 小 T 不会出题。

小 T 手中有一个数 $x$，初始时为 $p$。而小 ⊥ 手中有一个长为 $n$ 的序列 $a$。一次操作中，小 T 需要依次进行如下的修改： - 选中 $a$ 中的一个数 $a_i$。 - 将 $x$ 加上 $a_i$。 - 让 $a_i$ 变为自身的相反数，即 $-a_i$。 小 T 想知道，在若干次操作（可以不进行操作，同一个位置可以选中多次）之后，小 T 手中的数 $x$ 最大是多少。

无

无

**【样例解释 #1】** 对于样例，你可以依次执行以下操作： - 选中 $a_5=1$，$x$ 变为 $3+1=4$，$a_5$ 变为 $-1$。 - 选中 $a_1=1$，$x$ 变为 $4+1=5$，$a_1$ 变为 $-1$。 - 选中 $a_3=-4$，$x$ 变为 $5-4=1$，$a_3$ 变为 $4$。 - 选中 $a_4=5$，$x$ 变为 $1+5=6$，$a_4$ 变为 $-5$。 - 选中 $a_2=1$，$x$ 变为 $6+1=7$，$a_2$ 变为 $-1$。 - 选中 $a_3=4$，$x$ 变为 $7+4=11$，$a_3$ 变为 $-4$。 可以证明 $x$ 的最大值为 $11$。注意，并不是只有样例中展示的方案可以达到这个最大值。 **【数据范围】** |测试点编号|$n\le$|特殊性质| |:-:|:-:|:-:| |$1\sim3$|$20$|| |$4\sim5$|$10^5$|$a_i