You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

单调不下降的菜园

题目描述

WFYZ有一块长条形的菜园,可以看作是$1 \times n$个方格，从左往右第 $i$ 个可以种植品种 $a_i$，菜地不能更换种菜的品种。

小容是菜园兼职管理员，没空种太多的菜。他只想种恰好 $k$ 种菜，而且要菜的品种编号从左到右是单调不下降的，而且选择了一个品种后，每块这个品种的菜地都要种上。

小容种第 $i$ 种菜，会有 $b_i$价值的收获，他种菜能获得的最大价值总和是多少？

输入格式

第一行两个整数 $n,k$，表示菜园的大小和小容种菜的种类。 第二行 $n$ 个整数 $a_i$，表示菜地从左往右第 $i$ 个格子可以种菜的品种。 第三行 $n$ 个整数 $b_i$，表示第 $i$ 种菜可以获得的价值。

输出格式

一行一个整数，表示小容能够获得的最大价值；当然，如果没有符合要求的种菜方案，输出 $-1$。

样例 #1

样例输入 #1

5 2
1 2 1 3 2
5 3 1 100 100

样例输出 #1

6

样例 #2

样例输入 #2

10 3
1 3 4 2 9 3 4 2 5 1
1 5 2 3 9 8 1 2 3 10

样例输出 #2

-1

提示

【样例解释 #1】

对于第一组样例，我们可以选择 $1$ 号和 $3$ 号品种的菜地，种的菜为 $[1,1,3]$，满足单调不下降这一个限制，获得的价值即为 $b_1+b_3=5+1=6$，这是最优的办法。

【数据范围】

对于所有测试数据，满足 $1 \le n \le 500$，$1 \le k \le 500$，$1 \le a_i \le n$，$1 \le b_i \le 10^9$。

本题捆绑测试，所有数据范围均相同的测试点捆绑为一个 $\text{Subtask}$。

各测试点的附加限制如下表所示。