AT_joig2025_a カードゲーム 4 (Card Game 4)

カード $ 1 $ からカード $ N $ までの番号が付けられている $ N $ 枚のカードがある．各カードには $ 1 $ つの整数が書かれており，カード $ i $ ( $ 1 \leqq i \leqq N $ ) に書かれた整数は $ A_i $ である． これからあなたは， $ N $ 枚のカードから $ K $ 枚のカードを選ぶ．このとき，あなたの**得点**は以下のようになる． - 選んだカードに書かれた整数の偶奇がすべて同じ場合，選んだ $ K $ 枚のカードに書かれた整数の総和とする． - そうでない場合， $ 0 $ とする． カードの情報が与えられたとき，得点としてありうる最大値を求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

得点としてありうる最大値を $ 1 $ 行に出力せよ．

### 小課題 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 $ 点) 追加の制約はない． ### Sample Explanation 1 カード $ 1, 2, 3, 4, 5 $ の $ 5 $ 枚のカードを選ぶことを考える．このとき，選んだカードに書かれた整数はすべて奇数であるため，この選び方の得点は $ 1 + 1 + 1 + 1 + 1 = 5 $ である． カードの選び方の中で，得点が $ 6 $ 以上となるものはない．したがって， $ 5 $ を出力する． この入力例はすべての小課題の制約を満たす． ### Sample Explanation 2 あなたがどのように $ K $ 枚のカードを選んでも得点は $ 0 $ となる．したがって， $ 0 $ を出力する． この入力例は小課題 $ 2, 4 $ の制約を満たす． ### Sample Explanation 3 カード $ 1, 2, 6 $ の $ 3 $ 枚のカードを選ぶことを考える．このとき，選んだカードに書かれた整数はすべて奇数であるため，この選び方の得点は $ 3 + 7 + 5 = 15 $ である． カード $ 2, 3, 5 $ の $ 3 $ 枚のカードを選ぶことを考える．このとき，選んだカードに書かれた整数はすべて奇数であるため，この選び方の得点は $ 7 + 9 + 7 = 23 $ である． カードの選び方の中で，得点が $ 24 $ 以上となるものはない．したがって， $ 23 $ を出力する． この入力例は小課題 $ 3, 4 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 4 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 100\,000 $ ． - $ 1 \leqq K \leqq N $ ． - $ 1 \leqq A_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - 入力される値はすべて整数である．