P1704 Find the Most Elegant Problem-Solving Curve

nodgd is a student who enjoys programming. Some time ago (well, maybe not that recently), Luogu OJ came into being. Of course, nodgd started solving problems on Luogu OJ right away. A series of interesting events followed, and he decided to turn them into a problem to bother everyone.

Luogu OJ has a fun judging feature that automatically draws a user's "problem-solving curve." This curve is a polyline defined as follows: suppose a user solved $c_{b_i}$ problems on day $b_i$, where $b_i$ are strictly increasing. Then the user's problem-solving curve is the polyline passing through the points $(i, c_{b_i})$ in order. For example, if you solved $3$ problems on day $1$, $4$ on day $3$, and $1$ on day $6$, then your problem-solving curve over the first $6$ days is the continuous polyline from $(1, 3)$ to $(2, 4)$ to $(3, 1)$. nodgd can predict how many problems he would be able to AC on each of the next $N$ days. He also has an obsession with being strictly increasing, so he forces his problem-solving curve to be strictly increasing. For some reasons, on certain days (a total of $K$ days), he must solve problems, and the number of problems solved on those days must exactly match the predicted numbers (showcasing nodgd’s divine prediction). He wants to know, under these constraints, the maximum number of days on which he can solve problems. However, since he still has a pile of math, physics, English, art, and PE competition problems to do, he is asking you to compute it for him.

- The first line contains two positive integers $N$ and $K$, meaning nodgd has predictions for the next $N$ days, among which $K$ days are mandatory. - The second line contains $K$ distinct positive integers $p_i$, indicating that day $p_i$ is mandatory (the $p_i$ are not guaranteed to be in increasing order). - The third line contains $N$ positive integers $c_i$, where on day $i$, if nodgd solves problems, the number must be exactly $c_i$.

Output a single line. - If a strictly increasing problem-solving curve can be constructed, output a single positive integer: the maximum number of days on which nodgd can solve problems. - If no strictly increasing curve exists, output `impossible`.

Constraints For all testdata, - $1 \le N \le 500000$, $1 \le K \le N/2$； - $1 \le p_i \le N$, and all $p_i$ are distinct; the $p_i$ are not guaranteed to be in increasing order； - $1 \le c_i \le 10^9$。 Translated by ChatGPT 5