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 n cards in total, each with a suit c and a value v, with no more than k different suits. These cards are placed into a queue one by one at the end. If, before placing a card, there is already a card of the same suit in the queue, you may choose to remove all cards between this card and any one of the same suit (including these two cards themselves) from the queue, 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 queue, determine the maximum score she can obtain.

The input order represents the sequence in which LCR places the cards into the queue. That is, c_i denotes the suit of the i-th card placed, and v_i denotes 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