The Strongest Teams for IKPC

Task

The IKPC is right around the corner.
The kindergarten teacher, Theresa, wants to form some teams for the competition.
There are $N$ children in her class, and she wants to form exactly $K$ teams.

The children are sitting along a line, numbered from $0$ to $N-1$, according to their position in the line.
Child $i$ has a team play factor $A_i$ and a programming skill $B_i$.

Each team must have at least one member, and no child can be assigned to multiple teams.
Children $0 \le i_1 < i_2 < \ldots < i_l < N$ (for some $l>0$) can form a team if for each $1 \le p < l$ the following conditions hold:

• $A_{i_p} < A_{i_{p+1}}$, and
• there is no child with index $i_p < x < i_{p+1}$ such that $A_{i_p} < A_x$.

The strength of a team formed this way is $B_{i_1} + B_{i_2} + \ldots + B_{i_l}$.

Your task is to find the maximum possible sum of team strengths that Theresa can achieve by forming exactly $K$ teams!

Input data

The input file consists of:

• a line containing integers $N$, $K$.
• a line containing the $N$ integers $A_{0}, \, \ldots, \, A_{N-1}$.
• a line containing the $N$ integers $B_{0}, \, \ldots, \, B_{N-1}$.

Output data

The output file must contain a single line consisting of 64-bit integer $ans$.

Constraints and clarifications

• $1 \le K \le N \le 10^5$.
• $1 \le A_i \le N$ for each $i=0\ldots N-1$.
• $-10^9 \le B_i \le 10^9$ for each $i=0\ldots N-1$.
• IKPC stands for the International Kindergarten Programming Contest

Example 1

stdin

4 1
1 2 2 3
10 -10 -2 3

stdout

10

Explanation

In the first sample case forming the team consisting only of the first child is optimal.

Example 2

stdin

5 2
5 2 4 3 2
4 3 3 4 3

stdout

10

Explanation

In the second sample case forming one team consisting of the first child and another team consisting of the second and third children is optimal.