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