UOJ Logo

NOI.AC

#67. 刷题

统计

刷题

你打开了某著名 OJ 准备刷题。

这个 OJ 上一共有 $n$ 道题,并且你知道你刷第 $i$ 道题会获得 $a_i$ 的智慧值。对于每道题你都有两种选择:嘴巴切题和老实码完,第 $i$ 题老实码完需要花费时间 $t_i$,但是嘴巴切它只需要花费 $\lceil \frac{t_i}{2} \rceil$。一道题不管是嘴巴切还是老实码,都可以获得智慧值,但是你也不想做一个嘴巴选手,所以你允许自己最多嘴巴切 $w$ 个题。

你算了下自己总共有 $S$ 的时间,并且你有强迫症,只想从某道题开始顺着往下做,也就是你只想做连续一段的题。问在这 $S$ 时间内最多可以获得多少智慧值。

输入格式

第一行三个整数 $n,w,S$。

后面一行 $n$ 个整数表示 $a_i$。

后面一行 $n$ 个整数表示 $t_i$。

输出格式

一行一个整数表示这组数据的答案,也就是输出最大可获得的智慧值。

样例1

输入

7 2 15
8 6 7 4 10 7 10 
5 1 8 2 6 4 9

输出

35

样例2

样例数据

数据范围

10% $n\le 200$

另10% $n\le 5000$

另20% $w\le 3$

另20% $w\le 20$

100% $1\le w\le n \le 200000,1\le S \le 2\cdot 10^9$ $0\le a_i,t_i \le 10^4$