Excitation of Atoms

题意翻译

有 $n$ 个原子，编号为 $1-n$，初始每个原子都处于稳定态,但是他们可以被充能从而处于激发态。（姑且这么翻译吧） 要充能原子 $i$ 需要花费 $D_i$ 的能量，如果原子 $i$ 被充能，它会释放出 $A_i$ 的能量。你可以充能任意数量的原子（包括 $0$） 这些原子形成了**单向**键，对于一个原子 $i$，如果它被充能，则原子 $E_i$ 可以不花费任何代价获得充能。初始 $\forall i \in [1,n),E_i=i+1$ 你需要恰好改变 $k$ 次键，每次可以把 $E_i$ 改为不为 $i$ 和当前 $E_i$ 的原子。注意，$k$ 次操作之后键可以保持不变，一条键也可以被改变多次。你需要最大化可以获得的能量。 注意：你需要先改变恰好 $k$ 次键之后才能开始充能。 简要题意： 给定初始为一条链的的有向图，每个节点有代价和收益。如果支付了一个节点的代价可以获得它和所有它能到达的点的收益。不允许自环，链尾不允许有出边。在恰好改变 $k$ 次边之后求最大收益。

题目描述

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 < 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 < 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.

输入输出格式

输入格式

The first line contains two integers $ N $ $ K $ $ (4 \le N \le 10^5, 0 \le K < 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 $ .

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

35

说明

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.