E - Kth Takoyaki Set

コンテスト時間: 2023-04-09(日) 12:00 ~ 2023-04-09(日) 13:40 (100分) AtCoderホームへ戻る

E - Kth Takoyaki Set 解説

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : $500$ 点

問題文

AtCoder 王国では、 $N$ 種類のたこ焼きが売られています。 $i$ 種類目のたこ焼きの値段は $A_i$ 円です。

高橋君は、合計で $1$ 個以上のたこ焼きを買います。このとき、同じたこ焼きを複数個買うことも許されます。

高橋君が支払う金額としてあり得るもののうち、安い方から $K$ 番目の金額を求めてください。ただし、同じ金額を支払う方法が複数存在する場合は $1$ 回だけ数えます。

制約

$1 \le N \le 10$
$1 \le K \le 2 \times 10^5$
$1 \le A_i \le 10^9$
入力はすべて整数

入力

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

 $N$   $K$ 
 $A_1$   $A_2$   $\dots$   $A_N$

出力

答えを整数として出力せよ。

入力例 1Copy

Copy

4 6
20 25 30 100

出力例 1Copy

Copy

AtCoder 王国で売られている $4$ 種類のたこ焼きは、それぞれ $20$ 円、 $25$ 円、 $30$ 円、 $100$ 円です。

高橋君の支払う金額としてあり得るものは、安い方から $6$ 個を列挙すると $20$ 円、 $25$ 円、 $30$ 円、 $40$ 円、 $45$ 円、 $50$ 円となります。よって、答えは $50$ 円です。

合計で $1$ 個以上たこ焼きを買う必要があることに注意してください。

入力例 2Copy

Copy

2 10
2 1

出力例 2Copy

Copy

同じ金額の買い方が何通りかあっても、重複してカウントしないことに注意してください。

入力例 3Copy

Copy

10 200000
955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872

出力例 3Copy

Copy

5705443819

Score : $500$ points

Problem Statement

In AtCoder Kingdom, $N$ kinds of takoyakis (ball-shaped Japanese food) are sold. A takoyaki of the $i$ -th kind is sold for $A_i$ yen.

Takahashi will buy at least one takoyaki in total. He is allowed to buy multiple takoyakis of the same kind.

Find the $K$ -th lowest price that Takahashi may pay. Here, if there are multiple sets of takoyakis that cost the same price, the price is counted only once.

Constraints

$1 \le N \le 10$
$1 \le K \le 2 \times 10^5$
$1 \le A_i \le 10^9$
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

 $N$   $K$ 
 $A_1$   $A_2$   $\dots$   $A_N$

Output

Print the answer as an integer.

Sample Input 1Copy

Copy

4 6
20 25 30 100

Sample Output 1Copy

Copy

The four kinds of takoyakis sold in AtCoder Kingdom cost $20$ yen, $25$ yen, $30$ yen, and $100$ yen.

The six lowest prices that Takahashi may pay are $20$ yen, $25$ yen, $30$ yen, $40$ yen, $45$ yen, and $50$ yen. Thus, the answer is $50$ .

Note that at least one takoyaki must be bought.

Sample Input 2Copy

Copy

2 10
2 1

Sample Output 2Copy

Copy

Note that a price is not counted more than once even if there are multiple sets of takoyakis costing that price.

Sample Input 3Copy

Copy

10 200000
955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872

Sample Output 3Copy

Copy

5705443819