CF1425E Excitation of Atoms

Chanek 先生正在参加镇上非常受欢迎的科学展览。他在展览中发现了一个令人兴奋的谜题，并想要将其解开。 有 $N$ 个原子，编号从 $1$ 到 $N$。这些原子非常奇特。最初，每个原子都处于正常状态。每个原子都可以被激发。激发第 $i$ 个原子需要 $D_i$ 能量。当第 $i$ 个原子被激发时，它会释放 $A_i$ 能量。你可以激发任意数量的原子（包括零个）。 这些原子之间还形成了一种特殊的单向键。对于每个 $i$，$(1 \le i < N)$，如果第 $i$ 个原子被激发，则第 $E_i$ 个原子也会被激发，且不需要消耗能量。最初，$E_i = i+1$。注意，第 $N$ 个原子不能与任何原子形成键。 Chanek 先生必须恰好改变 $K$ 个键。恰好 $K$ 次，Chanek 先生选择一个原子 $i$，$(1 \le i < N)$，并将 $E_i$ 改为除 $i$ 和当前 $E_i$ 以外的另一个值。注意，一个原子的键可以保持不变，也可以被多次更改。请帮助 Chanek 先生确定他能够获得的最大能量！ 注意：你必须先恰好更改 $K$ 个键，然后才能开始激发原子。

第一行包含两个整数 $N$ 和 $K$，$(4 \le N \le 10^5, 0 \le K < N)$，分别表示原子的数量和必须更改的键的数量。 第二行包含 $N$ 个整数 $A_i$，$(1 \le A_i \le 10^6)$，表示第 $i$ 个原子被激发时释放的能量。 第三行包含 $N$ 个整数 $D_i$，$(1 \le D_i \le 10^6)$，表示激发第 $i$ 个原子所需的能量。

输出一行一个整数，表示 Chanek 先生能够获得的最大能量。

一种最优的方案是将 $E_5$ 改为 $1$，然后用能量 $1$ 激发原子 $5$。这将导致原子 $1, 2, 3, 4, 5$ 都被激发。Chanek 先生获得的总能量为 $(5 + 6 + 7 + 8 + 10) - 1 = 35$。 另一种可能的方式是将 $E_3$ 改为 $1$，然后激发原子 $3$（这会激发原子 $1, 2, 3$），再激发原子 $4$（这会激发原子 $4, 5, 6$）。Chanek 先生获得的总能量为 $(5 + 6 + 7 + 8 + 10 + 2) - (6 + 7) = 25$，这不是最优解。 由 ChatGPT 4.1 翻译