問題文

カード 1 からカード N までの番号が付けられている N 枚のカードがある．各カードには 1 つの整数が書かれており，カード i (1 \leqq i \leqq N) に書かれた整数は A_i である．

これからあなたは，N 枚のカードから K 枚のカードを選ぶ．このとき，あなたの得点は以下のようになる．

• 選んだカードに書かれた整数の偶奇がすべて同じ場合，選んだ K 枚のカードに書かれた整数の総和とする．
• そうでない場合，0 とする．

カードの情報が与えられたとき，得点としてありうる最大値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 100\,000．
• 1 \leqq K \leqq N．
• 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (30 点) N = K．
2. (25 点) A_i \leqq 2 (1 \leqq i \leqq N)．
3. (20 点) A_i は奇数である (1 \leqq i \leqq N)．
4. (25 点) 追加の制約はない．

入力例 1

5 5
1 1 1 1 1

出力例 1

5

カード 1, 2, 3, 4, 5 の 5 枚のカードを選ぶことを考える．このとき，選んだカードに書かれた整数はすべて奇数であるため，この選び方の得点は 1 + 1 + 1 + 1 + 1 = 5 である．

カードの選び方の中で，得点が 6 以上となるものはない．したがって，5 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 2

6 4
1 2 1 1 2 2

出力例 2

0

あなたがどのように K 枚のカードを選んでも得点は 0 となる．したがって，0 を出力する．

この入力例は小課題 2, 4 の制約を満たす．

入力例 3

7 3
3 7 9 1 7 5 3

出力例 3

23

カード 1, 2, 6 の 3 枚のカードを選ぶことを考える．このとき，選んだカードに書かれた整数はすべて奇数であるため，この選び方の得点は 3 + 7 + 5 = 15 である．

カード 2, 3, 5 の 3 枚のカードを選ぶことを考える．このとき，選んだカードに書かれた整数はすべて奇数であるため，この選び方の得点は 7 + 9 + 7 = 23 である．

カードの選び方の中で，得点が 24 以上となるものはない．したがって，23 を出力する．

この入力例は小課題 3, 4 の制約を満たす．

入力例 4

10 3
23 19 21 20 22 18 22 22 24 27

出力例 4

71

この入力例は小課題 4 の制約を満たす．