Largest sum after k sign flips

Problem

You must flip the sign of exactly one number in a list, k times in a row. The same number may be flipped again. Print the largest sum you can reach.

Input: Line 1: the numbers, separated by spaces. Line 2: k.
Output: One integer.
Constraints: 1 ≤ numbers ≤ 100000
-1000000 ≤ each number ≤ 1000000
0 ≤ k ≤ 1000000

Example 1

Input

4 2 3
1

Output

Example 2

Input

3 -1 0 2
3

Output

Try the problem first. Open one hint at a time.

Hint 1

Flipping the smallest number each time is the best move.

Hint 2

Use a min-heap: pop the smallest, flip it, push it back, k times.

Write your Python code, run it on the examples and submit it to hidden tests.