该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

有 $N（\le2\times 10^5）$ 种食材，编号从 $1$ 至 $N$，其中第 $i$ 种食材的美味度为 $a_i$。

另外有 $M（0\le M <2^{30}）$ 克秘制调料，如果某种食材使用 $a$ 克调料腌制，就可以使该食材美味度增加 $a$ ，调料按需使用，不需要全部用完。

选 $K$ 种食材做一道菜，不同食材之间的组合可能产生奇妙的化学反应，菜的最终美味度是所使用所有食材的美味度的与。

如何合理选择食材并腌制，使用最终菜肴的美味度最高。

Format

Input

第一行三个正整数 $N$ 、$M$ 和 $K$，分别表示食材种类、调料数量和烹制一道菜肴所需要的食材的种类数。

第二行给出每种食材的美味度 $a_i(\le2^{30})$ 。

Output

菜肴美味度的最大值。

Samples

6 114514 3
1 1 4 5 1 4

38175

Limitation

1s, 1024KiB for each test case.