Music in Car
Contest: Codeforces Round 386 (Div. 2)
Difficulty rating: 2200
Tags: data structures, greedy, two pointers

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 ai. The i-th song lasts for ti 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 $$\left\lceil \frac{d}{2} \right\rceil$$ 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 ai.

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.

Input format:
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 a1, a2, ..., an (1 ≤ ai ≤ 104), where ai equals the pleasure Sasha gets after listening to the i-th song.

The third line contains n positive integers t1, t2, ..., tn (2 ≤ ti ≤ 104), where ti equals the length of the i-th song in minutes.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
7 2 11
3 4 3 5 1 4 6
7 7 3 6 5 3 9

Example output:
12

Example input:
8 4 20
5 6 4 3 7 5 4 1
10 12 5 12 14 8 5 8

Example output:
19

Editorial:
This problem can be solved with help of two pointers. We will store two sets — set with songs with full time and set with songs with partly time. How to move left and right pointers and recalculate current answer? Let left end of the current segment is l and right end of the segment is r. Let the set of songs with partly time is half and with full time — full. In this sets we will store pairs — time of listening each song and it number.
Right end we will move in the following way: if we can add partly song and we have enough time to listen it — we take it (also add this song to half) and add to time (tr + 1) / 2 and add to the answer ar. In the other case we have two cases. First — we add current song as full song, second — we add current song as partly song. Here we need to choose case with less with the total time. Also here we need to correctly add song to sets and update total time and the answer. If total time became more than k we are not allowed to move r. Now we need to update global answer with the current value of answer.
Left end we will move in the following way: if we took song as full song we delete it from full, subtract from total time length of this song. In the other case we delete it from half and subtract from the total time the (tl + 1) / 2. After that we try to take some song from full. If the size of full is 0, we can not do that. If we done it we need to change total time on the songs on the current segment.