CF746F Music in Car

Sasha 开车去上班需要恰好 $k$ 分钟。在路上他会听音乐。他的播放列表里的所有歌曲会一首接一首播放，听完第 $i$ 首歌后，他能获得的愉悦值为 $a_i$。第 $i$ 首歌的时长为 $t_i$ 分钟。 在出发前，Sasha 会选中播放列表中的某一首歌 $x$ 开始播放，然后依次听接下来的歌：首先是第 $x$ 首歌，然后是第 $x+1$ 首歌，再然后是第 $x+2$ 首歌，依此类推。他会一直听下去，直到到达公司，或者播放列表中的最后一首歌已播放完。 Sasha 可以选择把一首歌听完整，也可以只听部分。 当选择只听部分时，他听这首歌的时间必须是整数分钟，并且至少要听满这首歌一半的时间。形式化地说，如果该歌时长为 $d$ 分钟，则 Sasha 必须至少听 $\left\lceil \frac{d}{2} \right\rceil$ 分钟，然后立即切换到下一首歌（如果有的话）。例如，如果一首歌的时长是 $5$ 分钟，则他至少要听 $3$ 分钟；如果一首歌的时长是 $8$ 分钟，则他至少要听 $4$ 分钟。 切换歌曲无需耗时。 Sasha 最多能选择 $w$ 首歌只听部分。如果最后一首歌实际听的时间少于其一半，则不会获得该歌的愉悦值，并且该歌不被计入“部分听完”的歌曲数。禁止跳过任意一首歌。无论是整首还是部分听完，所获得愉悦值都等于 $a_i$。 请你帮 Sasha 选择一个最合适的起始歌曲 $x$ 以及至多 $w$ 首进行部分聆听的歌曲，使得在上班路上获得的愉悦值最大。请编写程序，输出 Sasha 能获得的最大愉悦值。

第一行包含三个整数 $n$、$w$ 和 $k$（$1 \leq w \leq n \leq 2 \cdot 10^5$，$1 \leq k \leq 2 \cdot 10^9$），分别表示播放列表中的歌曲数、Sasha 最多能只听部分的歌曲数，以及去上班所需的分钟数。 第二行包含 $n$ 个正整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^4$），其中 $a_i$ 表示第 $i$ 首歌带来的愉悦值。 第三行包含 $n$ 个正整数 $t_1, t_2, ..., t_n$（$2 \leq t_i \leq 10^4$），其中 $t_i$ 表示第 $i$ 首歌的时长（分钟）。

输出一个整数，表示 Sasha 在上班路上最多能获得的愉悦值。

在第一个样例中，Sasha 应该从第 $2$ 首歌开始听。他应该选择只听 $4$ 分钟第 $2$ 首歌，然后完整听第 $3$ 首歌（$3$ 分钟），再只听 $3$ 分钟第 $4$ 首歌。这样一共获得的愉悦值是 $4 + 3 + 5 = 12$。Sasha 没有时间听第 $5$ 首歌，因为在听完第 $2$、$3$ 和 $4$ 首歌后共用时 $4 + 3 + 3 = 10$ 分钟，此后只剩 $1$ 分钟，无法满足部分聆听的最小时长要求。 由 ChatGPT 5 翻译