← 返回题目列表

Codeforces · 2003/F

F. 海龟和三个序列

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

Piggy 给 Turtle 三个序列 $$$a_1, a_2, \ldots, a_n$$$, $$$b_1, b_2, \ldots, b_n$$$ 和 $$$c_1, c_2, \ldots, c_n$$$。

Turtle会选择一个子序列$$$1, 2, \ldots, n$$$,长度为$$$m$$$,设其为$$$p_1, p_2, \ldots, p_m$$$。子序列应满足以下条件:

- $$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_m}$$$;
- 所有索引 $$$i$$$ 的所有 $$$b_{p_i}$$$ 都是成对不同的,即不存在两个不同的索引 $$$i$$$、$$$j$$$ 使得 $$$b_{p_i} = b_{p_j}$$$。

帮他求 $$$\sum\limits_{i = 1}^m c_{p_i}$$$ 的最大值,或者告诉他不可能选出满足上述条件的长度为 $$$m$$$ 的子序列。

回想一下,如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得,那么序列 $$$a$$$ 是序列 $$$b$$$ 的子序列。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 3000$$$, $$$1 \le m \le 5$$$) — 三个序列的长度和子序列所需的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 序列 $$$a$$$ 的元素。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — 序列 $$$b$$$ 的元素。

第四行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^4$$$) — 序列 $$$c$$$ 的元素。

输出

输出单个整数 — $$$\sum\limits_{i = 1}^m c_{p_i}$$$ 的最大值。如果无法选出满足上述条件的长度$$$m$$$的子序列,则输出$$$-1$$$。

示例

输入 #1

4 2
2 3 4 2
1 3 3 2
1 4 2 3

输出 #1

5

输入 #2

7 3
1 4 5 2 3 6 7
1 2 2 1 1 3 2
1 5 6 7 3 2 4

输出 #2

13

输入 #3

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

输出 #3

-1

注意

在第一个示例中,我们可以选择 $$$p = [1, 2]$$$,然后 $$$c_{p_1} + c_{p_2} = 1 + 4 = 5$$$。我们不能选择 $$$p = [2, 4]$$$,因为 $$$a_2 > a_4$$$,这违反了第一个条件。我们也不能选择 $$$p = [2, 3]$$$,因为 $$$b_2 = b_3$$$ 违反了第二个条件。我们可以选择 $$$p = [1, 4]$$$,但是 $$$c_1 + c_4 = 4$$$,这不是最大值。

在第二个示例中,我们可以选择 $$$p = [4, 6, 7]$$$。

在第三个示例中,不可能选择满足这两个条件的长度 $$$3$$$ 的子序列。