【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$ 最大是多少。
输入输出格式
输入格式
第一行两个整数 $n,p$。
第二行 $n$ 个整数 $a_i$。
输出格式
输出一行仅一个整数,表示 $x$ 最大是多少。
输入输出样例
输入样例 #1
6 3
1 1 -4 5 1 -4
输出样例 #1
11
输入样例 #2
7 4
1 -9 -1 -9 8 -1 0
输出样例 #2
13
说明
**【样例解释 #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<0$|
|$6\sim7$|$10^5$|$a_i\ge0$|
|$8\sim10$|$10^5$||
对于 $100\%$ 的数据,$1\le n\le10^5$,$|a_i|,|p|\le 10^9$。