Description

One day, Shen Ben and CFF were playing poker. They were playing 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, with no more than k different suits. These cards are placed one by one at the end of a sequence of cards. Before placing a card, if there is already a card with the same suit in the sequence, you may choose to remove all the cards between this card and any one of the cards with the same suit (including these two cards themselves) from the sequence, and gain a score equal to the sum of the values of all the removed cards. Now, given the order in which LCR places these n cards into the sequence, determine the maximum score she can obtain.

The input order is the order in which LCR places the cards into the sequence. That is, c_i represents the suit of the i-th card placed, and v_i represents the value of the i-th card placed.

Please note, if you are familiar with similar card games, 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 on one line, representing the maximum score that can be obtained.

```input1 7 3 1 2 1 2 3 2 3 1 2 1 2 3 2 3 ``` ```output1 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