텍스트 알고리즘

매년 Władek 선생님은 고등학생을 위한 과학 캠프에 초청되어 프로그래밍을 주제로 여러 차례 강의를 합니다. 선생님이 가장 좋아하는 주제는 물론 문자열 알고리즘입니다. 강의가 끝날 때마다 청중은 그날 강의와 크든 작든 연관이 있는 문제를 풀어야 합니다. 이번에 선생님은 오직 최고의 실력자만이 그 안에 숨은 "텍스트적인 요소"를 알아챌 수 있으리라 여기는 문제를 준비했습니다. 문제는 다음과 같습니다.

단위 정사각형으로 이루어진 직사각형 판이 있습니다. 각 행과 각 열에는 저마다 하나의 색이 정해져 있습니다. 가장 오른쪽 아래 칸에 말 하나가 놓여 있습니다. 한 번의 이동에서 말은 왼쪽으로 한 칸, 위쪽으로 한 칸, 또는 왼쪽 위 대각선으로 한 칸 움직일 수 있습니다. 왼쪽 이동과 위쪽 이동은 언제나 비용이 1입니다. 말이 현재 놓여 있는 칸의 행과 열의 색이 서로 같다면 대각선 이동은 무료(비용 0)입니다. 반대로 행과 열의 색이 서로 다르면 대각선 이동의 비용은 1입니다. 말을 시작 위치인 오른쪽 아래 칸에서 왼쪽 위 칸까지 옮기는 데 드는 최소 비용은 얼마입니까?

첫 번째 줄에 두 자연수 $n$, $m$이 주어집니다 ($1 \le n, m \le 100000$, $n \cdot m \le 10^7$). 여기서 $n$은 판의 행 개수이고, $m$은 열을 색이 같은 구간으로 묶어 나타낸 그룹의 개수입니다.

다음 $n$개의 줄에는 위에서 아래로 각 행의 색이 한 줄에 하나씩 주어집니다. $i$번째 줄에는 $i$번째 행의 색을 나타내는, $10^6$ 이하의 자연수 하나가 있습니다.

이어지는 $m$개의 줄에는 왼쪽에서 오른쪽으로 열의 색이 구간 단위로 주어집니다. $i$번째 줄에는 공백 하나로 구분된 두 자연수 $d_i$, $k_i$가 있습니다 ($1 \le d_i, k_i \le 10^6$). 이는 다음 $d_i$개의 열이 모두 색 $k_i$를 가진다는 뜻입니다. 열의 총 개수는 $2 \cdot 10^9$ 이하입니다.

오른쪽 아래 칸에서 출발하여 왼쪽 위 칸에 도달하는 데 드는 최소 비용을 한 줄에 정수 하나로 출력합니다.

위 그림은 하나의 예시 판을 보여 줍니다. 글자 P는 말의 시작 위치를 나타내며, 경로에 적힌 숫자들은 그 지점까지 수행한 이동의 누적 비용입니다.