| Codeforces Round 386 (Div. 2) |
|---|
| Закончено |
Саша ездит на работу на машине, и дорога занимает ровно k минут. По дороге он слушает музыку. Все песни в его плейлисте расположены друг за другом и от прослушивания i-й из них Саша получает удовольствие равное ai. При этом i-я песня длится ti минут.
Перед началом пути Саша включит произвольную песню под номером x, и будет слушать песни по очереди: сначала песню под номером x, затем песню под номером (x + 1), затем песню под номером (x + 2), и так далее. Он будет слушать песни пока не приедет на работу, либо пока не послушает последнюю песню из своего плейлиста.
Каждую песню Саша может либо прослушать полностью, либо прослушать ее частично. Во втором случае он слушает песню целое число минут хотя бы половину её длительности. Формально, если длина песни равна d минут, то Саша послушает ее в течение не менее 
минут, а затем сразу переключит на следующую песню (если она есть). Например, если длина песни, которую Саша будет слушать частично, равна 5 минутам, то он должен послушать её хотя бы 3 минуты, а если длина песни равна 8 минутам — хотя бы 4 минуты.
Переключение песен происходит мгновенно.
При этом Саша согласен прослушать частично не более w песен. Если последняя прослушанная песня играла менее, чем половину своей длительности, то она не приносит Саше удовольствия и не учитывается в песнях, прослушанных частично. Пропускать песни нельзя. Удовольствие от песни не зависит от режима ее прослушивания, для i-й песни эта величина равна ai.
Помогите Саше выбрать такое x и выбрать не более w песен для частичного прослушивания, чтобы он получил максимальное удовольствие. Напишите программу находящую максимальное удовольствие, которое может получить Саша, от прослушивания песен по дороге на работу.
В первой строке следуют три целых числа n, w и k (1 ≤ w ≤ n ≤ 2·105, 1 ≤ k ≤ 2·109) — количество песен в плейлисте, количество песен, которые Саша согласен послушать частично и время в минутах, за которое Саша доезжает до работы.
Во второй строке следуют n целых положительных чисел a1, a2, ..., an (1 ≤ ai ≤ 104), где ai равно удовольствию, которое Саша получит от прослушивания i-й песни.
В третьей строке следуют n целых положительных чисел t1, t2, ..., tn (2 ≤ ti ≤ 104), где ti равно длительности i-й песни в минутах.
Выведите максимальное удовольствие, которое может получить Саша, от прослушивания песен по дороге на работу.
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
В первом примере Саше нужно начать прослушивание с песни номер 2. Ее он должен прослушать частично (за 4 минуты), затем полностью прослушать песню номер 3 (за 3 минуты) и потом частично прослушать песню номер 4 (за 3 минуты). После прослушивания этих песен Саша получит удовольствие равное 4 + 3 + 5 = 12. Песню номер 5 Саша прослушать не успеет, так как потратит на прослушивание песен 2, 3 и 4 время равное 4 + 3 + 3 = 10 минутам и до работы останется ехать всего 1 минуту.
