CF746F.Music in Car

Sasha reaches the work by car. It takes exactly k minutes. On his way he listens to music. All songs in his playlist go one by one, after listening to the i-th song Sasha gets a pleasure which equals a__i. The i-th song lasts for t__i minutes.

Before the beginning of his way Sasha turns on some song x and then he listens to the songs one by one: at first, the song x, then the song (x + 1), then the song number (x + 2), and so on. He listens to songs until he reaches the work or until he listens to the last song in his playlist.

Sasha can listen to each song to the end or partly.

In the second case he listens to the song for integer number of minutes, at least half of the song's length. Formally, if the length of the song equals d minutes, Sasha listens to it for no less than minutes, then he immediately switches it to the next song (if there is such). For example, if the length of the song which Sasha wants to partly listen to, equals 5 minutes, then he should listen to it for at least 3 minutes, if the length of the song equals 8 minutes, then he should listen to it for at least 4 minutes.

It takes no time to switch a song.

Sasha wants to listen partly no more than w songs. If the last listened song plays for less than half of its length, then Sasha doesn't get pleasure from it and that song is not included to the list of partly listened songs. It is not allowed to skip songs. A pleasure from a song does not depend on the listening mode, for the i-th song this value equals a__i.

Help Sasha to choose such x and no more than w songs for partial listening to get the maximum pleasure. Write a program to find the maximum pleasure Sasha can get from the listening to the songs on his way to the work.

萨沙开车去上班，全程恰好需要 $k$ 分钟。途中他听音乐。他的播放列表中所有歌曲按顺序依次播放，听完第 $i$ 首歌后，萨沙获得的愉悦值为 $a_i$。第 $i$ 首歌的时长为 $t_i$ 分钟。

出发前，萨沙会选定某一首歌 $x$ 开始播放，之后按顺序连续收听：先听第 $x$ 首歌，再听第 $(x+1)$ 首歌，接着是第 $(x+2)$ 首歌，依此类推。他持续听歌，直到抵达公司，或播放完播放列表中的最后一首歌为止。

萨沙可以完整听完每首歌，也可以只听其中一部分。

在后者情形下，他必须听整数分钟，且至少听满该歌曲总时长的一半。形式化地说，若某首歌时长为 $d$ 分钟，则萨沙至少需听 分钟，之后立即切换到下一首歌（如果存在）。例如，若某首歌时长为 5 分钟，则至少需听 3 分钟；若时长为 8 分钟，则至少需听 4 分钟。

切换歌曲不消耗时间。

萨沙最多只能对至多 $w$ 首歌进行部分收听。若最后一首被收听的歌曲播放时长不足其总时长的一半，则萨沙无法从中获得任何愉悦值，且该歌曲也不计入“部分收听”的歌曲数量中。不允许跳过任何歌曲。每首歌带来的愉悦值与其收听方式无关，第 $i$ 首歌的愉悦值恒为 $a_i$。

请帮助萨沙选择起始歌曲编号 $x$，并至多对 $w$ 首歌进行部分收听，以使总愉悦值最大化。编写程序求出萨沙在上班途中听歌所能获得的最大愉悦值。

The first line contains three integers n, w and k (1 ≤ w ≤ n ≤ 2·105, 1 ≤ k ≤ 2·109) — the number of songs in the playlist, the number of songs Sasha can listen to partly and time in minutes which Sasha needs to reach work.

The second line contains n positive integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 104), where a__i equals the pleasure Sasha gets after listening to the i-th song.

The third line contains n positive integers _t_1, _t_2, ..., t__n (2 ≤ t__i ≤ 104), where t__i equals the length of the i-th song in minutes.

第一行包含三个整数 $n$、$w$ 和 $k$（$1 ≤ w ≤ n ≤ 2·10^5$，$1 ≤ k ≤ 2·10^9$）—— 分别表示播放列表中的歌曲数量、Sasha 可以部分收听的歌曲数量，以及 Sasha 到达工作地点所需的时间（单位：分钟）。

第二行包含 $n$ 个正整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 10^4$），其中 $a_i$ 表示 Sasha 听完第 $i$ 首歌后获得的愉悦值。

第三行包含 $n$ 个正整数 $t_1, t_2, ..., t_n$（$2 ≤ t_i ≤ 10^4$），其中 $t_i$ 表示第 $i$ 首歌的时长（单位：分钟）。

Print the maximum pleasure Sasha can get after listening to the songs on the way to work.

输出 Sasha 在上班途中听歌所能获得的最大快乐值。

In the first example Sasha needs to start listening from the song number 2. He should listen to it partly (for 4 minutes), then listen to the song number 3 to the end (for 3 minutes) and then partly listen to the song number 4 (for 3 minutes). After listening to these songs Sasha will get pleasure which equals 4 + 3 + 5 = 12. Sasha will not have time to listen to the song number 5 because he will spend 4 + 3 + 3 = 10 minutes listening to songs number 2, 3 and 4 and only 1 minute is left after that.

在第一个例子中，萨沙需要从第 2 首歌开始听。他应先部分收听第 2 首歌（时长为 4 分钟），然后完整收听第 3 首歌（时长为 3 分钟），再部分收听第 4 首歌（时长为 3 分钟）。在收听完这些歌曲后，萨沙获得的快乐值为 $4 + 3 + 5 = 12$。萨沙将没有时间收听第 5 首歌，因为他收听第 2、3、4 首歌总共花费了 $4 + 3 + 3 = 10$ 分钟，之后仅剩 1 分钟。