102974: [Atcoder]ABC297 E - Kth Takoyaki Set

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:4 Solved:0

Description

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

Input

题意翻译

### 题目描述 AtCoder 王国出售 $N$ 种类的章鱼烧。第 $i$ 种章鱼烧的价格是 $A_i$ 日元。 高桥一共买了 $1$ 个以上的章鱼烧。这个时候,也允许买多个同样的章鱼烧。 高桥君可以支付的金额中,请从便宜的一方寻求第 $K$ 的金额。但是,如果存在多个支付相同金额的方法,则只计算$ 1 $个。 ### 输入格式 输入以以下形式由标准输入给出。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ ### 输出格式 把答案作为整数输出。 ### 示例#1 ### 样例输入#1 ``` 4 6 20 25 30 100 ``` ### 样例输出#1 ``` 50 ``` ## 示例#2 ### 样例输入#2 ``` 2 10 2 1 ``` ### 样例输出#2 ``` 10 ``` ## 样例#3 ### 样例输入#3 ``` 10 200000 955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872 ``` ### 样例输出#3 ``` 5705443819 ``` ## 提示 ### 约束条件 - $ 1\ \le\ N\ \le\ 10 $ - $ 1\ \le\ K\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ A_i\ \le\ 10^9 $ - 所有输入均为整数 ### Sample Explanation 1 AtCoder王国出售的4个种类的章鱼烧,分别是$ 20 $日元、$ 25 $日元、$ 30 $日元、$ 100 $日元。高桥君支付的金额可能是,从便宜的一方列举$ 6 $个的话,$ 20 $日元,$ 25 $日元,$ 30 $日元,$ 40 $日元,$ 45 $日元,$ 50 $日元。因此,答案是$ 50 $个日元。请注意总共需要买$ 1 $个以上的章鱼烧。 ### Sample Explanation 2 请注意,即使有几种相同金额的购买方法,也不要重复计算。

Output

分数:500分

问题描述

在AtCoder王国,出售$N$种章鱼烧(一种日本食品)。第$i$种章鱼烧售价为$A_i$日元。

Takahashi将总共购买至少一个章鱼烧。他可以购买同一种类的多个章鱼烧。

找出Takahashi可能支付的第$K$低价格。如果有多套章鱼烧价格相同,则只计算一次价格。

约束

  • $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王国出售的四种章鱼烧的价格分别为20日元、25日元、30日元和100日元。

Takahashi可能支付的六种最低价格分别为20日元、25日元、30日元、40日元、45日元和50日元。因此,答案是50。

请注意,必须至少购买一个章鱼烧。


样例输入2

2 10
2 1

样例输出2

10

即使有多套章鱼烧价格相同,价格也不会被计算多次。


样例输入3

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

样例输出3

5705443819

加入题单

上一题 下一题 算法标签: