D-「Nhk R1 D」Apocryphal Vir Pulcher_牛客练习赛94

「Nhk R1 D」Apocryphal Vir Pulcher

比赛主页

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在最后给出了形式化题意。

WA！GAAY！是一个风靡全球的比赛。成千上万的 Gaays 参加这个 OI 比赛，由于 Gaays 实在是太强了，所以她们都 AK 了。

但是，她们并没有一次成型，反而，她们中的某些 WA 了很多发。每次 WA 掉 $i$ 题会掉 $a_i$ rating。众所周知，Gaays 中的内卷很严重，扣的分数不是前 $k$ 小的都会被淘汰。这引起的她们的恐慌，所以她们想知道，第 $k$ 小的扣分到底会是多少。值得一提的是，没有任何一对 Gaays 在每一题WA的次数都相同。

Gaays 找到了你来帮忙，还说不帮忙就把你也变成 Gaay。请你帮帮她们吧。

形式化题意：给出一个长度为 $n$ 的序列 $\{a_i\}$ 。现在可以给出无限组长度为 $n$ 的序列 $\{c_i\geqslant0\}$ 。

定义两个序列 $P$ ， $Q$ 相等当且仅当 $\forall i$ ，有 $P_i=Q_i$ 。

对于所有不相等的 $\{c_j\}$ ，可以求出一个序列 $\{x_i=\sum\limits_{j=1}^{n}a_jc_j\}$ ，求 $\{x_i\}$ 中的第 $k$ 小值。

输入描述:

输入共两行。

第一行两个整数表示 $n$ 和 $k$ 。

第二行输入序列 $a_1 \sim a_n$ 。

输出描述:

一行一个整数，表示第  小值。

示例1

输入

复制

3 5
1 2 3

输出

复制

说明

最后的  是：

取其中第  小值，即 。

示例2

输入

复制

3 10
2 3 4

输出

复制

说明

对于 $20\%$ 的数据， $n \le 10$ ， $2 \le k \le 10^5$ 。

对于另外 $20\%$ 的数据， $n \le 30$ ， $2 \le k \le 10^5$ 。

对于 $100\%$ 的数据， $n \le 80$ ， $2 \le k \le 10^6$ ， $1\leqslant a_i\leqslant10^6$ 。