You are playing a computer game called "Best Alternating" where you have to fight N monsters numbered from $1$ to N$.$

You are given an array of integers A where A$[$i$]$ represents the energy each monster has. It is given that the energy of a monster can also be negative.

You have to fight all monsters from monster numbered $1$ to monster numbered N in order and if you fight a monster numbered i$,$ your score will increase by A$[$i$].$

Initially, you start with score as zero. But, you have a special ability called Alternating, which means that initially you have a positive sign $"+"$ to add all the monster's energies. Then, at any moment of time $($even before meeting the first monster$)$ you can decide to change this sign to $"-",$ and keep alternating this way for K times.

The final sum of energies obtained will be your score.

For example: If N$=2,$ K$=1$ and A$=[10,-10]$

We can alternate the sign when we meet the second monster. Hence score $=+[+10]-[-10]=20$

Find the maximum score that you can get by playing$$optimally$.$

Note:

$$ The sign chosen will remain the same until it is alternated.

Input Format

The first line contains an integer, N$,$ denoting the number of elements in A$.$

The next line contains an integer, K$,$ denoting the given integer.

Each line i of the N subsequent lines $($where $0<=$ i $<$ N $)$ contains an integer describing A$[$i$].$

Constraints

$1<=$ N $<=10^5$

$0<=$ K $<=100$

$-10^4<=$A$[$i$]<=10^4$

Sample Test Cases

Case $1$

Input:

$5$

$1$

$10$

$-10$

$10$

$10$

$10$

Output:

$30$

Explanation:

Given N$=5,$ K$=1,$ A $=[10,-10,10,10,10].$

In this sample, if we don't alternate the sign at all, the answer will be $"30"$ as:

$"+[+10]+[-10]+[+10]+[10]+[10]=30".$

Case $2$

Input:

$5$

$2$

$10$

$-10$

$10$

$10$

$10$

Output:

$50$

Explanation:

Given N$=5,$ K $=2,$ A $=[10,-10,10,10,10].$

This is the same as the first sample but here $"$k$"$ is two, so we can alternate the sign twice and the answer will be calculated as the following:

$+[+10]-[-10]+[+10]+[+10]+[+10]=50.$

Case $3$

Input:

$5$

$3$

$-100$

$100$

$-200$

$10$

$-10$

Output:

$400$

Explanation:

Given N $=5,$ K $=3,$ A$=[-100,100,-200,10,-10].$

Initially, we start with a positive sign as the problem statements says, but when we meet the first monster we will alternate it to $"-"$ and add $"100"$ to the score.

Then we will alternate it to $"+"$ when meeting the second monster, and then to $"-$"when meeting the third monster, and thus, we have changed the sign K$=3$ times.

Thus, the answer is calculated as follows: $-[-100]+[+100]-[-200]-[+10]-[-10]=400".$

Write this problem in Java code with explanation.