← 返回题目列表

Codeforces · 1425/E

E. 原子的激发

中文机器翻译题面 查看原题

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$$$ 之外的不同值。请注意,原子的键可以保持不变或多次改变。帮助查内克先生确定他可以达到的最大能量!

注意:您必须首先准确更改 $$$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$$$所需的能量。

输出

一行有一个整数,表示查内克先生可以获得的最大能量数。

示例

输入 #1

6 1
5 6 7 8 10 2
3 5 6 7 1 10

输出 #1

35

注意

最优解是将$$$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)。 Chanek 先生获得的总能量为 (5 + 6 + 7 + 8 + 10 + 2) - (6 + 7) = 25,这不是最优的。