外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

C - Nyan cafe in Nyan star

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 250 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

問題文

わりとねこくんは、ねこ星で MM 店舗のねこカフェを経営しています。
ねこ星には NN 匹のねこがおり、それぞれ 11 から NN までの番号がつけられています。ねこ ii のかわいさは CiC_i です。

わりとねこくんは、経営するすべてのねこカフェにちょうど KK 匹ずつねこをお迎えすることにしました(ここで、N=M×KN = M \times K であることが保証されています)。

各ねこカフェにねこを配分したとき、そのねこカフェの魅力度は、そのカフェにいる KK 匹のねこの中で最もかわいさが低いねこのかわいさと同じになります。

わりとねこくんが適切にねこを配分したとき、すべてのねこカフェの魅力度の総和の最大値を求めてください。

制約

  • 1≤N,M,K≤2×1051 \le N, M, K \le 2 \times 10^5
  • N=M×KN = M \times K
  • 1≤Ci≤1091 \le C_i \le 10^9
  • 入力はすべて整数

入力

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

NMKN \quad M \quad K C1C2⋯CNC_1 \quad C_2 \quad \cdots \quad C_N

出力

すべてのねこカフェの魅力度の総和の最大値を 11 行に出力してください。

サンプル 1

入力

6 2 3
1 2 3 4 5 6

出力

5

11店舗目のねこカフェに1,2,31,2,3匹目のねこを、 22店舗目のねこカフェに4,5,64,5,6匹目のねこを配分した時の魅力度の総和は min⁡(1,2,3)+min⁡(4,5,6)=5\min (1,2,3) + \min (4,5,6) = 5 となり、これ以上魅力度を大きくすることはできないので、答えは55になります。

サンプル 2

入力

6 3 2
5 2 6 3 1 4

出力

9

サンプル 3

入力

9 3 3
22 47 22 29 4 30 38 36 31

出力

69

参加受付は終了しました。