A83464.上课不要睡觉

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

你和朋友 Mishka\text{Mishka} 正在上微积分课,这节课一共持续 nn 分钟。第 ii 分钟老师会讲 aia_i 条定理。

给定一个长度为 nn 的数组 tt 来描述 Mishka\text{Mishka} 每分钟的状态:

  • 若在第 ii 分钟他睡着,则 ti=0t_i=0
  • 清醒,则 ti=1t_i=1

当他清醒时,会把这一分钟老师讲的定理全部记下来(获得 aia_i 的“收益”);当他睡着时,这一分钟就什么也记不到。

你掌握一种秘密技巧,能让 Mishka\text{Mishka} 连续保持清醒恰好 kk 分钟,但只能使用一次。你可以选择在任意一分钟的开始启动它(只要完整的 kk 分钟区间没有超出整节课范围)。在这段被技巧覆盖的区间里,无论原本他是否会睡着,都将视为清醒并获得相应的 aia_i

请计算:如果你把这项技巧使用在最合适的时段,Mishka\text{Mishka} 最多能记下多少条定理。

输入格式

第一行:两个整数 n,kn, k

第二行:nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n

第三行:nn 个整数 t1,t2,,tnt_1, t_2, \dots, t_n(仅为 0011)。

输出格式

一行一个整数,表示在最优使用这项技巧的前提下,Mishka 最多能记下的定理总数。

输入输出样例

  • 输入#1

    6 3
    1 3 5 2 5 4
    1 1 0 1 0 0
    

    输出#1

    16
    

说明/提示

1kn1051 \le k \le n \le 10^5

1ai1041 \le a_i \le 10^4

0ti10 \le t_i \le 1

对于样例:

原本清醒的分钟会直接获得对应的 aia_i;而你可以选择一个长度为 k=3k=3 的连续区间把他“强制清醒”。若从第 3 分钟开始使用(覆盖第 3–5 分钟),则:

原本清醒得到的和:第 1241、2、4 分钟 → 1+3+2=61+3+2=6

叫醒区间中原本会睡着的分钟也能获得:第 353、5 分钟 → 5+5=105+5=10
合计 6+10=166+10=16,这是最优方案。

首页