Text Algorithms

Every year Wladek is invited to a science camp for high-school students to give a series of lectures on programming. His favorite topic is, of course, string algorithms. After each lecture the audience has to solve a task that is related, to a greater or lesser degree, to the lecture. This time Wladek prepared a problem in which, in his opinion, only the very best contestants will notice the hidden "textual" nature. The statement goes as follows.

You are given a rectangular board made of unit squares. Every row and every column has its own color. A pawn stands on the bottom-right square. In a single move the pawn can go one square left, one square up, or one square along the upper-left diagonal. Moving left and moving up always cost 1. If the row and the column the pawn currently stands on have the same color, the diagonal move is free (cost 0). Otherwise, when the colors of the row and the column differ, the diagonal move costs 1. What is the smallest possible cost of moving the pawn from its start position, the bottom-right square, to the top-left square?

The first line contains two natural numbers $n$ and $m$ ($1 \le n, m \le 100000$, $n \cdot m \le 10^7$). Here $n$ is the number of rows of the board, and $m$ is the number of groups (runs) into which the columns are packed by equal color.

The next $n$ lines describe the colors of the rows from top to bottom. The $i$-th of them contains a single natural number, not greater than $10^6$, the color of the $i$-th row.

The following $m$ lines describe the colors of the columns from left to right, run by run. The $i$-th of them contains two natural numbers $d_i$ and $k_i$ ($1 \le d_i, k_i \le 10^6$) separated by a single space. They mean that the next $d_i$ columns all have color $k_i$. The total number of columns is at most $2 \cdot 10^9$.

Print a single integer: the smallest possible cost of moving the pawn from the bottom-right square to the top-left square.

The picture shows one sample board. The letter P marks the pawn's starting position, and the numbers along the path are the running total cost of the moves made so far.