解题思路

题目给出连续 n 个周期，每个周期有：

• update_cost[i]：本周期执行“更新”的成本（正整数）
• query_reward[i]：本周期执行“查询”的收益（非负整数，只有知识库有效时才有）

知识库规则：

题目内容

在基于 $RAG$ (检索增强生成) 技术的智能问答系统中，知识库的时效性直接影响查询服务的质量。系统每天(周期)可通过更新知识库维持其有效性，或基于当前知识库处理用户查询获取收益。由于更新知识库需要消耗计算资源(如文档嵌入、索引重建)，而查询收益仅在知识库有效的情况下才能获得，因此需要动态平衡“更新成本"与“查询收益”，制定最优运营策略。

给定 $n$ 个连续周期，第 $i$ 个周期 $i (0≤i ＜n)$ 有两个参数；

$update\_cost[i]$：第 $i$ 周期更新知识库的成本(正整数)。

$query\_reward[i]$：第 $i$ 周期使用当前知识库处理查询的收益(非负整数)，仅当知识库有效时可获得。

核心规则：

知识库有效期：每次更新后，知识库进入“有效状态”，有效期持续 $d$ 个 周期(含更新所在周期)。例如：若 $d=2$ ，第 $3$ 周期更新后，第 $3、4$ 周期有效，第 $5$ 周期过期。

操作选择：每个周期可执行如下操作之一:

仅查询：若知识库有效，获得 $query\_reward[i]$ 收益，无成本；若知识库过期，收益为 $0$ 。

仅更新：支付 $update\_cost[i]$ 成本，重置有效期(从当前周期开始持续 $d$ 个周期)，无直接收益。

先更新后查询：支付 $update\_cost[i]$ 成本，获得 $query\_reward[i]$ 收益(更新后立即有效)

暂停：无成本，无收益，知识库状态不变(如果当前周期知识库有效，暂停会消耗一个有效周期;过期则保持过期)。

初始状态：知识库初始为“过期”状态(第 $0$ 周期若要查询，必须先更新)。

目标：计算 $n$ 个连续周期内可获得的最大净利润(总收益 - 总更新成本)。

输入描述

第一行为连续周期数 $n$ 和持续周期 $d$ ，用空格隔开

第二行为 $update\_cost$ 数组，用空格隔开

第三行为 $query\_reward$ 数组，用空格隔开

输出描述

最大净利润，整数

样例1

输入

3 2
100 100 100
1 1 1

输出

0

样例2

输入

3 3
10 20 30
5 10 15

输出

20

说明

在 $3$ 个周期中，最优策略是：

周期 $0$ ：更新并查询(利润：$-5$ )

周期 $1$ ：查询 (利润：$+10$ )

周期 $2$ ：查询 (利润： $+15$ ) 最终累计最大净利润为 $20$ 。

提示

$1≤n≤10^5$ (至少 $1$ 个周期)

$1≤d≤n$ (折扣间隔 $d$ ，有效期持续 $d$ 个周期)

$1≤update\_cost[i]≤10^4$ (正整数，每个周期的更新成本至少为 $1$ )

$0≤query\_reward[i]≤ 10^4$ (非负整数，收益可零但不可为负)