CF2003F Turtle and Three Sequences

Piggy gives Turtle three sequences $ a_1, a_2, \ldots, a_n $ , $ b_1, b_2, \ldots, b_n $ , and $ c_1, c_2, \ldots, c_n $ . Turtle will choose a subsequence of $ 1, 2, \ldots, n $ of length $ m $ , let it be $ p_1, p_2, \ldots, p_m $ . The subsequence should satisfy the following conditions: - $ a_{p_1} \le a_{p_2} \le \cdots \le a_{p_m} $ ; - All $ b_{p_i} $ for all indices $ i $ are pairwise distinct, i.e., there don't exist two different indices $ i $ , $ j $ such that $ b_{p_i} = b_{p_j} $ . Help him find the maximum value of $ \sum\limits_{i = 1}^m c_{p_i} $ , or tell him that it is impossible to choose a subsequence of length $ m $ that satisfies the conditions above. Recall that a sequence $ a $ is a subsequence of a sequence $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) elements.

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 3000 $ , $ 1 \le m \le 5 $ ) — the lengths of the three sequences and the required length of the subsequence. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the elements of the sequence $ a $ . The third line contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \le b_i \le n $ ) — the elements of the sequence $ b $ . The fourth line contains $ n $ integers $ c_1, c_2, \ldots, c_n $ ( $ 1 \le c_i \le 10^4 $ ) — the elements of the sequence $ c $ .

Output a single integer — the maximum value of $ \sum\limits_{i = 1}^m c_{p_i} $ . If it is impossible to choose a subsequence of length $ m $ that satisfies the conditions above, output $ -1 $ .

In the first example, we can choose $ p = [1, 2] $ , then $ c_{p_1} + c_{p_2} = 1 + 4 = 5 $ . We can't choose $ p = [2, 4] $ since $ a_2 > a_4 $ , violating the first condition. We can't choose $ p = [2, 3] $ either since $ b_2 = b_3 $ , violating the second condition. We can choose $ p = [1, 4] $ , but $ c_1 + c_4 = 4 $ , which isn't maximum. In the second example, we can choose $ p = [4, 6, 7] $ . In the third example, it is impossible to choose a subsequence of length $ 3 $ that satisfies both of the conditions.