시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB56413272.727%

문제

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

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

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

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

입력

入力は以下の形式で与えられる.

N K

A1 A2 … AN

출력

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

제한

  • 1 ≦ N ≦ 100 000.
  • 1 ≦ K ≦ N.
  • 1 ≦ Ai ≦ 109 (1 ≦ i ≦ N).
  • 入力される値はすべて整数である.

서브태스크

번호배점제한
130

N = K.

225

Ai ≦ 2 (1 ≦ i ≦ N).

320

Ai は奇数である (1 ≦ i ≦ N).

425

追加の制約はない.

예제 입력 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 の制約を満たす.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.