Background

Original link: https://oier.team/problems/X3C。

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.

Problem Description

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$.

Input Format

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

The second line contains $n$ integers $a_i$.

Output Format

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

6 3
1 1 -4 5 1 -4

11

7 4
1 -9 -1 -9 8 -1 0

13

Hint

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

For $100\%$ of the data, $1 \le n \le 10^5$, $|a_i|, |p| \le 10^9$.

Translated by ChatGPT 5