AT_ttpc2015_b ラー油

东工太郎君在 $N$ 天里，每天都会吃一碗担担面。担担面可以根据喜好添加任意量的辣油。太郎君在第 $i$ 天（$1 \leq i \leq N$）吃了加了 $x_i$ 辣油的担担面时，可以获得 $A_i x_i$ 的幸福度。 由于太郎君肠胃较弱，需要满足 $0 \leq x_i \leq B\ (1 \leq i \leq N)$ 且 $\sum_{1 \leq i \leq N} x_i \leq C$。另外，辣油非常美味，所以当 $N \geq 2$ 时，对于任意的 $i(1 \leq i \leq N-1)$，都有 $A_i \leq A_{i+1}$。 请你求出太郎君在 $N$ 天内能够获得的幸福度总和的最大值。

输入通过标准输入给出，格式如下： > $N$ $B$ $C$ $A_1$ $...$ $A_N$ - 第 $1$ 行包含三个整数 $N(1 \leq N \leq 100)$、$B(1 \leq B \leq 10000)$、$C(1 \leq C \leq 10000)$，以空格分隔。 - 第 $2$ 行包含 $N$ 个整数 $A_1, \ldots, A_N\ (0 \leq A_i \leq 100)$，以空格分隔。 - 当 $N \geq 2$ 时，对于任意的 $i(1 \leq i \leq N-1)$，都有 $A_i \leq A_{i+1}$。

请输出太郎君在 $N$ 天内能够获得的幸福度总和的最大值，输出占一行，末尾需换行。

### 样例解释 1 第 $1$ 天加 $1$ 份辣油，第 $2$ 天和第 $3$ 天各加 $2$ 份辣油是最优的，太郎君能获得 $11$ 的幸福度。 ### 样例解释 2 第 $1$ 天和第 $2$ 天都不加辣油，第 $3$ 天加 $100$ 份辣油是最优的，太郎君能获得 $10000$ 的幸福度。 ### 样例解释 3 太郎君无法再额外加辣油。 ### 样例解释 4 太郎君的肠胃太弱，无法再加辣油。 ### 样例解释 5 无论加多少辣油，太郎君都无法获得幸福。 由 ChatGPT 4.1 翻译