P11035 [MX-X3-T2] "RiOI-4" The Vanished Summer Dream

Original link: 。 --- > Let’s keep talking, just the two of us, forever\ About the summer that has ended,\ And gently bring the dreams we were searching for\ To an end, so that we never go back.\ It’s goodbye.\ The voice I wished would reach you\ Turned into the wind, and slipped through\ The gaps in my heart.\ —— "The Vanished Summer Dream" Xiao T cannot set problems.

Xiao T has a number $x$, which is initially $p$. Xiao $\bot$ has a sequence $a$ of length $n$. In one operation, Xiao T needs to perform the following changes in order: - Choose one number $a_i$ in $a$. - Add $a_i$ to $x$. - Set $a_i$ to its additive inverse, i.e., $-a_i$. Xiao T wants to know: after performing some operations (it is allowed to perform no operation, and the same position may be chosen multiple times), what is the maximum possible value of $x$.

The first line contains two integers $n, p$. The second line contains $n$ integers $a_i$.

Output one line with a single integer, representing the maximum possible value of $x$.

**Sample Explanation #1** For the sample, you can perform the following operations in order: - Choose $a_5 = 1$, then $x$ becomes $3 + 1 = 4$, and $a_5$ becomes $-1$. - Choose $a_1 = 1$, then $x$ becomes $4 + 1 = 5$, and $a_1$ becomes $-1$. - Choose $a_3 = -4$, then $x$ becomes $5 - 4 = 1$, and $a_3$ becomes $4$. - Choose $a_4 = 5$, then $x$ becomes $1 + 5 = 6$, and $a_4$ becomes $-5$. - Choose $a_2 = 1$, then $x$ becomes $6 + 1 = 7$, and $a_2$ becomes $-1$. - Choose $a_3 = 4$, then $x$ becomes $7 + 4 = 11$, and $a_3$ becomes $-4$. It can be proven that the maximum value of $x$ is $11$. Note that it is not only the plan shown in the sample that can achieve this maximum value. **Constraints** |Test Point ID|$n \le$|Special Property| |:-:|:-:|:-:| |$1 \sim 3$|$20$|| |$4 \sim 5$|$10^5$|$a_i < 0$| |$6 \sim 7$|$10^5$|$a_i \ge 0$| |$8 \sim 10$|$10^5$|| For $100\%$ of the data, $1 \le n \le 10^5$, $|a_i|, |p| \le 10^9$. Translated by ChatGPT 5