CF1425E.Excitation of Atoms

Mr. Chanek is currently participating in a science fair that is popular in town. He finds an exciting puzzle in the fair and wants to solve it.

There are $N$ atoms numbered from $1$ to $N$. These atoms are especially quirky. Initially, each atom is in normal state. Each atom can be in an excited. Exciting atom $i$ requires $D_i$ energy. When atom $i$ is excited, it will give $A_i$ energy. You can excite any number of atoms (including zero).

These atoms also form a peculiar one-way bond. For each $i$, $(1 \le i \lt N)$, if atom $i$ is excited, atom $E_i$ will also be excited at no cost. Initially, $E_i$ = $i+1$. Note that atom $N$ cannot form a bond to any atom.

Mr. Chanek must change exactly $K$ bonds. Exactly $K$ times, Mr. Chanek chooses an atom $i$, $(1 \le i \lt N)$ and changes $E_i$ to a different value other than $i$ and the current $E_i$. Note that an atom's bond can remain unchanged or changed more than once. Help Mr. Chanek determine the maximum energy that he can achieve!

note: You must first change exactly $K$ bonds before you can start exciting atoms.

陈克先生目前正在参加一场镇上颇受欢迎的科学博览会。他在博览会上发现了一个有趣的谜题，想要解开它。

共有 $N$ 个原子，编号从 $1$ 到 $N$。这些原子行为十分奇特：初始时，每个原子均处于正常状态；每个原子均可被激发为激发态。激发原子 $i$ 需要消耗 $D_i$ 能量，而一旦原子 $i$ 被激发，它将释放 $A_i$ 能量。你可以选择激发任意数量的原子（包括零个）。

此外，这些原子之间还形成一种特殊的单向键。对每个 $i$（其中 $1 \le i < N$），若原子 $i$ 被激发，则原子 $E_i$ 也将被免费激发（即无需额外能量）。初始时，$E_i = i+1$。注意：原子 $N$ 无法与任何其他原子形成键。

陈克先生必须恰好修改 $K$ 条键。具体而言，他需恰好执行 $K$ 次操作：每次选择一个原子 $i$（其中 $1 \le i < N$），并将 $E_i$ 修改为一个不同于 $i$ 且不同于当前 $E_i$ 的新值。注意：某原子的键可以保持不变，也可以被多次修改。请帮助陈克先生计算他所能获得的最大能量！

注意：你必须先恰好完成 $K$ 次键的修改，然后才能开始激发原子。

The first line contains two integers $N$ $K$ $(4 \le N \le 10^5, 0 \le K \lt N)$, the number of atoms, and the number of bonds that must be changed.

The second line contains $N$ integers $A_i$ $(1 \le A_i \le 10^6)$, which denotes the energy given by atom $i$ when on excited state.

The third line contains $N$ integers $D_i$ $(1 \le D_i \le 10^6)$, which denotes the energy needed to excite atom $i$.

第一行包含两个整数 $N$ 和 $K$ $(4 \le N \le 10^5, 0 \le K \lt N)$，分别表示原子的数量以及必须更改的化学键数量。

第二行包含 $N$ 个整数 $A_i$ $(1 \le A_i \le 10^6)$，表示第 $i$ 个原子处于激发态时所释放的能量。

第三行包含 $N$ 个整数 $D_i$ $(1 \le D_i \le 10^6)$，表示将第 $i$ 个原子激发所需的能量。

A line with an integer that denotes the maximum number of energy that Mr. Chanek can get.

一个整数，表示陈先生能获得的最大能量值。

An optimal solution to change $E_5$ to 1 and then excite atom 5 with energy 1. It will cause atoms 1, 2, 3, 4, 5 be excited. The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10) - 1 = 35.

Another possible way is to change $E_3$ to 1 and then exciting atom 3 (which will excite atom 1, 2, 3) and exciting atom 4 (which will excite atom 4, 5, 6). The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10 + 2) - (6 + 7) = 25 which is not optimal.

将 $E_5$ 改为 1，然后用能量 1 激发原子 5。这将导致原子 1、2、3、4、5 均被激发。陈先生获得的总能量为 $(5 + 6 + 7 + 8 + 10) - 1 = 35$。

另一种可行方案是：将 $E_3$ 改为 1，然后激发原子 3（这将激发原子 1、2、3）以及激发原子 4（这将激发原子 4、5、6）。陈先生获得的总能量为 $(5 + 6 + 7 + 8 + 10 + 2) - (6 + 7) = 25$，该方案并非最优。