萨莎开车到达工作地点。正好需要 k 分钟。他在路上听音乐。他的播放列表中的所有歌曲都一首一首地播放,听完第 i 首歌曲后,萨沙获得了相当于 ai 的快感。第 i 首歌曲持续 ti 分钟。
在开始他的旅程之前,Sasha 打开了一些歌曲 x,然后他一首一首地听这些歌曲:首先是歌曲 x,然后是歌曲 (x + 1),然后是歌曲编号 (x + 2),依此类推。他听歌曲直到他到达工作地点或直到他听播放列表中的最后一首歌曲。
Sasha 可以听完每首歌曲,也可以听一部分。
在第二种情况下,他听了歌曲的整数分钟,至少是歌曲长度的一半。形式上,如果歌曲的长度等于 d 分钟,Sasha 听它的时间不少于 $$\left\lceil \frac{d}{2} \right\rceil$$ 分钟,然后他立即切换到下一首歌曲(如果有的话)。例如,如果萨沙想要部分听的歌曲长度等于5分钟,那么他应该听至少3分钟,如果歌曲长度等于8分钟,那么他应该听至少4分钟。
切换歌曲不需要时间。
Sasha 只想听 w 首歌曲。如果最后听的歌曲播放的时间少于其长度的一半,则 Sasha 不会从中获得乐趣,并且该歌曲不会包含在部分收听的歌曲列表中。不允许跳过歌曲。歌曲的乐趣并不取决于聆听模式,对于第 i 首歌曲,该值等于 ai。
帮助Sasha选择x首且不超过w首歌曲进行部分聆听,以获得最大的乐趣。编写一个程序,找出萨沙在上班路上听歌曲时所能获得的最大乐趣。
输入
第一行包含三个整数 n、w 和 k (1 ≤ w ≤ n ≤ 2·105, 1 ≤ k ≤ 2·109) — 播放列表中的歌曲数、Sasha 可以部分收听的歌曲数以及 Sasha 上班所需的时间(以分钟为单位)。
第二行包含n个正整数a1, a2, ..., an (1 ≤ ai ≤ 104),其中ai等于Sasha听完第i首歌后获得的愉悦感。
第三行包含 n 个正整数 t1, t2, ..., tn (2 ≤ ti ≤ 104),其中 ti 等于第 i 首歌曲的长度(以分钟为单位)。
输出
打印萨莎在上班路上听完歌曲后获得的最大乐趣。
示例
输入 #1
7 2 11 3 4 3 5 1 4 6 7 7 3 6 5 3 9
输出 #1
12
输入 #2
8 4 20 5 6 4 3 7 5 4 1 10 12 5 12 14 8 5 8
输出 #2
19
输入 #3
1 1 5 6 9
输出 #3
6
输入#4
1 1 3 4 7
输出#4
0
注意
在第一个示例中,Sasha 需要从 2 号歌曲开始听。他应该听一部分(4 分钟),然后听 3 号歌曲到最后(3 分钟),然后部分听 4 号歌曲(3 分钟)。听完这些歌曲后,Sasha 会得到快乐,等于 4 + 3 + 5 = 12。 Sasha 没有时间听第 5 首歌曲,因为他会花 4 + 3 + 3 = 10 分钟听第 2、3、4 首歌曲,之后只剩下 1 分钟。