statement.md

Description

shiro君は進学振り分けの結果、情報理工学科に配属されることが決定しました。早速、新学期に向けて履修登録を考えなければなりません。 さて、shiro君は必修科目は全て登録し終えたので、今から専門選択科目をどれにするかを決める必要があります。

$N$個の専門選択科目があります。各科目には人気度という、その科目がどれくらい人気であるかを表す値が与えられており、人気度が高い科目ほど人気です。$i$番目の科目の人気度は$a_i$です。

shiro君は$K$個の科目を選択することにしたようです。

shiro君は人気な科目も取りたい一方、選外を避けて確実に科目を選択したい気持ちもあるので、$K$個の科目の人気度の合計値が$X$番目に大きいものになるように科目を選択することにしました。

$N$個の専門選択科目のうち$K$個を選んだとき、$X$番目に大きい人気度の合計値を出力して下さい。

ただし、人気度の合計値が同じでも組み合わせが違っていれば異なるものとして数え、また、各科目は1度しか選択できないものとします。

Constraints

• 入力はすべて整数である。
• $1 \leq a_i \leq 1000 (1 \leq i \leq N)$
• $1 \leq X \leq {}_N C_K $

Small

• $T = 5$
• $1 \leq K \leq N \leq 3$

Large

• $T = 50$
• $1 \leq K \leq N \leq 10$

Input

1つの入力ファイルは複数のテストケースからなる。

入力ファイルの最初の一行目にはテストケースの個数$T$が記される。

2行目以降には、$T$ 個のテストケースが記述されており、各テストケースは次の形式で表される。

$N$ $K$ $X$
$a_1$ $a_2$ $\ldots$ $a_i$ $a_{i+1}$ $\ldots$ $a_n$

Output

各テストケースに対して、答えを1行ずつ出力せよ。

Sample Input

2
3 1 2
1 2 3
5 3 3
1 2 3 4 5

Sample Output

2
10

入力例は2つのテストケースからなります。

• 1つめのテストケースについて、科目数は全部で3つあり、それぞれ人気度は

1 2 3

です。この中から科目を1つ選ぶので、あり得る人気度の合計値は大きい順に並べると、

3 2 1

となります。今回は2番目に大きい人気度の合計値を答えればよいので、2を出力します。

• 2つめのテストケースについて、科目数は全部で5つあり、それぞれ人気度は

1 2 3 4 5

です。この中から科目を3つ選ぶので、あり得る人気度の合計値は大きい順に並べると、

12 11 10 10 9 9 8 8 7 6

となります。今回は3番目に大きい人気度の合計値を答えれば良いので、10を出力します。