/ 
Time Limit: 3 sec / Memory Limit: 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
出力
答えを整数として出力せよ。
入力例 1
4 6 20 25 30 100
出力例 1
50
AtCoder 王国で売られている 4 種類のたこ焼きは、それぞれ 20 円、25 円、30 円、100 円です。
高橋君の支払う金額としてあり得るものは、安い方から 6 個を列挙すると 20 円、25 円、30 円、40 円、45 円、50 円となります。よって、答えは 50 円です。
合計で 1 個以上たこ焼きを買う必要があることに注意してください。
入力例 2
2 10 2 1
出力例 2
10
同じ金額の買い方が何通りかあっても、重複してカウントしないことに注意してください。
入力例 3
10 200000 955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872
出力例 3
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 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