DMPG '16 G4 - Araxxi

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
FatalEagle
Problem type

You are playing a game called RuinScape and are currently fighting a tough boss named Araxxi (she is a spider). The fight will last for N units of time. Araxxi has M types of special attacks that she uses, numbered from 1 to M, and she will use a single special attack during each of the N units of time. She always uses the same sequence of special attacks, and some special attacks may be repeated in this sequence more than once.

Since you are a skilled player, you know that the key to winning the fight is to counter as many of Araxxi's special attacks as you can. You know the techniques to counter each of the M special attacks. Once you activate a technique, all of Araxxi's special attacks that the technique counters will be countered, but you will be hit by all of Araxxi's other special attacks that she uses.

Activating a technique is done on the same unit of time as, but an infinitesimal amount of time before Araxxi's special attack (so if Araxxi uses the attack your technique counters on that unit of time, you will successfully counter it). You can switch techniques during the fight, but after cancelling a technique, there is a delay before you can activate the next technique, meaning you must take unavoidable damage from the special attacks that occur during the delay after you cancel the current technique. Specifically, if the delay has a value d, that means you cannot activate another technique until you take damage d times. This delay may be different for different techniques. If you play optimally, what is the maximum number of special attacks can you counter?

Input Specification

The first line of input will contain two integers N and M.
The second line of input will contain N integers, the sequence of special attacks Araxxi uses, in order. Each integer will be between 1 and M, inclusive.
The third line of input will contain M integers, the i^\text{th} of which is the delay for the technique to counter Araxxi's i^\text{th} attack. Each integer will be between 0 and N-1, inclusive.

Output Specification

The first and only line of output should contain the maximum number of special attacks you can counter.

Constraints

For all subtasks:

1 \le M \le N \le 100\,000

Subtask 1 [20%]

N \le 1000

Subtask 2 [20%]

M = 2

Subtask 3 [20%]

All the delays are equal to 1.

Subtask 4 [40%]

No additional constraints.

Sample Input

5 2
1 2 2 1 2
0 2

Sample Output

4

Explanation of Output for Sample Input

The optimal strategy is to activate the technique to counter type 1 special attacks just before Araxxi uses her first attack, and immediately after, switch to the technique to counter type 2 special attacks and keep using that technique until the end of the fight. You will get hit by one type 1 attack, but you will have managed to counter 4 attacks.

Comments