Music in Car

## 题意简述 萨沙在上班途中听歌，她最多听 $k$ 分钟。她可以从任意一首歌开始听，若从第 $x$ 首歌开始，就只能听第 $x,x+1,x+2,\cdots ,n$ 首歌，而不能听第 $x-1,x-2,\cdots$ 首歌。听第 $i$ 首歌会获得 $a_{i}$ 的快乐值。其中可以选择 $w$ 首歌，这些歌只要听到一半的时间就可以切换下一首，且仍然可以获得此歌的快乐值，但未到一半时间无法获得此歌的快乐值。需求出最大能获得的快乐值。 ## 输入格式 第一行三个数 $n$，$w$，$k$。（$1\le w\le n\le 2\times 10^5$，$1\le k\le 2\times 10^9$） 第二行 $n$ 个数 $a_{1},a_{2},\cdots ,a_{n}$。（$1\le a_{i}\le 10^4$） 第三行 $n$ 个数 $t_{1},t_{2},\cdots ,t_{n}$。第 $i$ 个数代表第 $i$ 首歌的时长。（$2\le t_{i}\le 10^4$）

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.

The first line contains three integers $ n $ , $ w $ and $ k $ ( $ 1<=w<=n<=2·10^{5} $ , $ 1<=k<=2·10^{9} $ ) — 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}<=10^{4} $ ), 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}<=10^{4} $ ), where $ t_{i} $ equals the length of the $ i $ -th song in minutes.

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

7 2 11
3 4 3 5 1 4 6
7 7 3 6 5 3 9

12

8 4 20
5 6 4 3 7 5 4 1
10 12 5 12 14 8 5 8

19

1 1 5
6
9

6

1 1 3
4
7

0

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.