Flipping Signs 2

2 secs 1024 MB
hotman78

この問題はFlipping Signsを元に作られたものです

まずはこちらから解くことをおすすめします

問題文


個の整数が並んでおり、順に です。

あなたはこの整数列に対して次の操作を好きなだけ行うことができます。

操作: を満たす整数 を選ぶ。 を乗算する。

操作終了後の整数列を とします。

の最大値を求めてください。

制約


  • 入力は全て整数である。

入力


入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 ... A_N

出力


の最大値を出力せよ。

入力例1


3 2
-10 5 -4

出力例1


19

提出


Go (1.14)