CF846B Math Show

Polycarp 参加了一场数学竞赛。他需要完成 $n$ 个大题，每个大题包含 $k$ 个子题，子题编号为 $1$ 到 $k$。他完成第 $j$ 个子题，无论属于哪个大题，都需花费 $t_{j}$ 分钟。也就是说，完成某一道大题中第 $j$ 个子题所需时间只与 $j$ 有关，与大题编号无关。Polycarp 可以按任意顺序解答子题。 每完成任意大题的一个子题，Polycarp 都能获得 $1$ 分。因此，他在一道题上获得的分数等于他完成的子题数。此外，如果 Polycarp 完成了某道大题的全部 $k$ 个子题，他可额外获得 $1$ 分。因此，完成一道大题所有子题可获得 $k+1$ 分。 Polycarp 共有 $M$ 分钟时间。他最多能获得多少分？

第一行包含三个整数 $n$、$k$ 和 $M$（$1 \leq n \leq 45$，$1 \leq k \leq 45$，$0 \leq M \leq 2 \cdot 10^{9}$）。 第二行包含 $k$ 个整数，表示 $t_{j}$（$1 \leq t_{j} \leq 1000000$），$t_{j}$ 表示完成任意一题的第 $j$ 个子题所需的分钟数。

输出在 $M$ 分钟内 Polycarp 能获得的最大分数。

在第一个样例中，Polycarp 可以完成第一道题，耗时 $1+2+3+4=10$ 分钟。他还可以用 $1$ 分钟完成第二道题的一个子题。 在第二个样例中，Polycarp 可以每道题都完成第一个子题，总共耗时 $5 \cdot 1=5$ 分钟。同时他还能完成两道题的第二个子题，总共耗时 $2 \cdot 2=4$ 分钟。所以他总共可以获得 $5 + 2 = 7$ 分。 由 ChatGPT 5 翻译