Start 2023-11-18 00:00:00

1118比赛

End 2023-11-25 00:00:00
Contest is over.
Now 2024-05-18 20:37:38

D. K 次取反后最大化的数组和

Description

给你一个整数数组 nums 和一个整数 k ,按以下方法修改该数组:

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后,返回数组 可能的最大和 。

Input

3 1 4 2 3

Output

5

Examples

Input

3 1
4 2 3

Output

5

Input

4 3
3 -1 0 2

Output

6

Input

5 2
2 -3 -1 5 -4

Output

13

Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit