P8919 "MdOI R5" Message

Little A has a group chat. The group is playing a small game: given a function $f$, starting from some time, when the $x$-th message is sent, any member for whom $f(x)=1$ will receive a small punishment. The game ends when the total number of messages in the group reaches $m$. However, Little A is very talkative. During this period, he sent $n$ messages in the group. The $i$-th message he sent is the $a_i$-th message in the entire message history. But Little A does not want to be punished, and he happens to be an administrator. He can recall **any message sent by any group member at any time**. Note that this will cause the rankings of all messages after that message to change. But recalling too many messages may be seen as tyranny, so he wants to minimize the number of recalled messages, no matter whether they are his own or others'. Now you can guess what you need to do: assuming other group members do nothing, given $n$, the function $f$, and $a_i$, find the minimum number of messages he must recall.

The first line contains two positive integers $n, m$, representing the number of messages sent by Little A and the total number of messages in the group. The second line is a **01 string** of length $m$, $f$, where the $i$-th character $f(i)$ indicates whether the sender of the $i$-th message will be punished. The third line contains $n$ positive integers $a_1, a_2, \ldots, a_n$, representing the initial rankings of each of Little A's messages. It is guaranteed that the sequence $a$ is strictly increasing and $1 \le a_i \le m$.

Output one line with an integer $ans$, the minimum number of messages that must be recalled so that Little A will not be punished.

[Sample Explanation] One possible way is: - Little A first recalls the $1$-st message (sent by another member). Now his four messages are the $1, 5, 7, 10$-th messages in the message history. - Then he recalls the $5$-th message (sent by himself). The remaining three messages are now the $1, 6, 9$-th messages in the message history. At this time, the three messages satisfy $f(1)=f(6)=f(9)=0$, which meets the requirement. It can be proven that it is impossible to achieve the goal by recalling only one message. [Constraints] |Subtask|$n\le$|$m\le$|Special Property|Score| |:-:|:-:|:-:|:-:|:-:| |1|$17$|$17$||$15$| |2|$17$|$100$||$15$| |3|$10^3$|$10^4$||$20$| |4||$10^5$|$n=m$|$8$| |5|$10^5$|$10^6$|A|$12$| |6|$10^5$|$10^6$||$30$| - Special Property A: Little A never sends two messages in a row. For all testdata, $1 \le n \le 10^5$, $1 \le a_i \le m \le 10^6$, $a_i$ is strictly increasing, and $f(i) \in \{0,1\}$. Translated by ChatGPT 5