坡旅甲参加数学表演。他被分配了 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 分。