U455494 为赋新词强说愁

Pam 国的 Pantro 正在作词，但他做的词......

Pantro 作的词很特殊，每个字都拥有一个愁度，记作 $ c_i $。 对于一些字组成的段落，段落愁度为所有字的愁度之积。 对于一些段落组成的词，词愁度为所有段落的愁度之和。 比如对于这样一段段落：`3 5`，它的愁度为 $ 3 \times 5 = 15 $。 又比如对于这样一段词：`3 5 7`，我们分成 `3 5` 和 `7 `，它的愁度就为 $3 \times 5 + 7 = 22$。而如果我们分成 `3` 和 `5 7 `，它的愁度为 $3 + 5 \times 7 = 38$。 Pantro 还有一个实际愁度 $ k $，如果词愁度大于 $ k $，那么这篇词就是「为赋新词强说愁」的。 Pantro 马上就要去参加隔壁 Moyoro 国的诗词大会了，请你帮他将词分成段落，使得他的词不是「为赋新词强说愁」的，且要使得词的愁度尽量高。 如果无论如何都无法避免「为赋新词强说愁」，输出 $ -1 $。 Pantro 想知道，分一段，分两段，分三段 ...... 分 $ m $ 段的最优解是什么。

一行三个整数 $n, m, k$ 接下来 $ m $ 个整数，代表字愁度。

一行 $ n $ 个整数，第 $ 1 \le i \le m$ 个数代表如果只能分 $ i $ 个段落的最优解。

对于第一组数据，$105, 38$ 是「为赋新词强说愁」的。 对于 $ 30 \%$ 的数据，$ 1 \le m \le 10, 1 \le n \le 100 $。 对于 $ 100 \%$ 的数据，$ 1 \le m \le 10^3, 1 \le n \le 10^3, 1 \le k \le 10^9 $。