← 返回题目列表

Codeforces · 846/B

B. 数学秀

中文机器翻译题面 查看原题

坡旅甲参加数学表演。他被分配了 n 个任务,每个任务由 k 个子任务组成,编号为 1 到 k。他需要 tj 分钟来解决任何任务的第 j 个子任务。因此,解决子任务所需的时间仅取决于其索引,而不取决于任务本身。 Polycarp 可以按任意顺序解决子任务。

通过解决任意问题的子任务,他可以获得一分。因此,任务的点数等于其中已解决的子任务的数量。此外,如果波利卡普完全解决了该任务(解决了所有 k 个子任务),他将获得一分。因此,他完成任务的总得分是 k + 1。

波利卡普有 M 分钟的时间。他最多可以获得多少积分?

输入

第一行包含三个整数 n、k 和 M (1 ≤ n ≤ 45, 1 ≤ k ≤ 45, 0 ≤ M ≤ 2·109)。

第二行包含 k 个整数,值 tj (1 ≤ tj ≤ 1000000),其中 tj 是解决任何任务的第 j 个子任务所需的时间(以分钟为单位)。

输出

打印 Polycarp 在 M 分钟内可以获得的最大积分。

示例

输入 #1

3 4 11
1 2 3 4

输出 #1

6

输入 #2

5 5 10
1 2 4 8 16

输出 #2

7

注意

在第一个示例中,Polycarp 可以完成第一个任务并花费 1 + 2 + 3 + 4 = 10 分钟。他还有时间在一分钟内解决第二个任务的一个子任务。

在第二个示例中,Polycarp 可以解决所有五个任务中的第一个子任务,并花费 5·1 = 5 分钟。他还可以解决两个任务的第二个子任务,并花费 2·2 = 4 分钟。因此,他总共获得 5 + 2 = 7 分。