Description

One day, Shen Ben and CFF were playing poker. They played a game called "Bamboo Connection."
The rules of the game are as follows: There are a total of n cards, each with a suit c and a value v. The number of suits does not exceed k. These cards are placed one by one at the end of a column of cards. If, before placing a card, there already exists a card of the same suit in the column, you may choose to remove all cards between this card and any other card of the same suit (including these two cards themselves) from the column and earn a score equal to the sum of the values of all removed cards. Now, given the order in which LCR places these n cards into the column, determine the maximum score she can obtain.
The input order corresponds to the order in which LCR places the cards into the column. That is, c_i represents the suit of the i-th placed card, and v_i represents the value of the i-th placed card.
Note: If you are familiar with similar card games, please read the rules especially carefully to avoid unnecessary issues due to misunderstanding the problem.

Input Format

The first line contains two integers, n and k.
The second line contains n integers, c_1, c_2, c_3, ..., c_n, representing the suits, where 1 ≤ c_i ≤ k.
The third line contains n integers, v_1, v_2, v_3, ..., v_n, representing the values.

Output Format

Output a single integer, representing the maximum score that can be obtained.

7 3
1 2 1 2 3 2 3
1 2 1 2 3 2 3

13

Hint

Sample 1 Explanation
Step 1: Add 1 to the queue. Current queue: 1;
Step 2: Add 2 to the queue. Current queue: 1, 2;
Step 3: Add 1 to the queue. Current queue: 1, 2, 1;
Step 4: Add 2 to the queue, then remove 2, 1, 2. Current queue: 1;
Step 5: Add 3 to the queue. Current queue: 1, 3;
Step 6: Add 2 to the queue. Current queue: 1, 3, 2;
Step 7: Add 3 to the queue, then remove 3, 2, 3. Current queue: 1.

Data Range and Test Points
For 100% of the data, 1 ≤ n ≤ 10^6, 1 ≤ k ≤ 10^6, 1 ≤ v_i ≤ 10^9.

Source

CodesOnline