日本情報オリンピック 第5回 女性部門

2025年2月8日
情報オリンピック日本委員会

問題文

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

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

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

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

制約

• 1 ≦ N ≦ 100 000．
• 1 ≦ K ≦ N．
• 1 ≦ A_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 入力される値はすべて整数である．

小課題

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

入力

入力は以下の形式で与えられる．
N K
A₁ A₂ … A_N

出力

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

入出力例

入力例 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 の制約を満たす．