Score : $500$ points

问题描述

在AtCoder王国中，售卖着$N$种不同类型的章鱼小丸子（日本球形小吃）。第$i$种章鱼小丸子的售价为$A_i$日元。

高桥将会总共购买至少一个章鱼小丸子。他可以购买同一种类的多个章鱼小丸子。

找出高桥可能支付的第$K$低价格。注意，如果有多种组合的章鱼小丸子价格相同，那么该价格只计算一次。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

In AtCoder Kingdom, $N$ kinds of _takoyaki_s (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 1

4 6
20 25 30 100

Sample Output 1

50

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 2

2 10
2 1

Sample Output 2

10

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

Sample Input 3

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

Sample Output 3

5705443819

update @ 2024/3/10 12:20:38