단조성

정수 수열 $a_1, a_2, \ldots, a_n$ 에 대해, 그 단조성 표식(monotonicity scheme) 을 기호 $<$, $>$, $=$ 로 이루어진 수열 $s_1, s_2, \ldots, s_{n-1}$ 로 정의한다. 기호 $s_i$ 는 $a_i$ 와 $a_{i+1}$ 사이의 대소 관계를 나타낸다. 예를 들어 수열 $2, 4, 3, 3, 5, 3$ 의 단조성 표식은 $<, >, =, <, >$ 이다.

단조성 표식이 $s_1, s_2, \ldots, s_n$ 인 정수 수열 $b_1, b_2, \ldots, b_{n+1}$ 이 다른 단조성 표식 $s'_1, s'_2, \ldots, s'_k$ 를 실현한다(realize) 는 것은, 모든 $i = 1, 2, \ldots, n$ 에 대해 $s_i = s'_{((i-1) \bmod k) + 1}$ 이 성립함을 뜻한다. 즉, 수열 $s_1, s_2, \ldots, s_n$ 은 수열 $s'_1, s'_2, \ldots, s'_k$ 를 반복한 뒤 알맞은 접미사를 잘라내어 얻을 수 있다. 예를 들어 수열 $2, 4, 3, 3, 5, 3$ 은 다음 표식들을 모두 실현한다.

• $<, >, =$
• $<, >, =, <, >$
• $<, >, =, <, >, <, <, =$
• $<, >, =, <, >, =, >, >$

이 외에도 많은 표식을 실현한다.

정수 수열 $a_1, a_2, \ldots, a_n$ 과 단조성 표식 $s_1, s_2, \ldots, s_k$ 가 주어진다. 주어진 수열의 부분 수열 $a_{i_1}, a_{i_2}, \ldots, a_{i_m}$ ($1 \le i_1 < i_2 < \cdots < i_m \le n$) 중에서 주어진 표식을 실현하는 가장 긴 것을 찾으시오.

첫째 줄에 수열 $(a_i)$ 의 길이와 단조성 표식 $(s_j)$ 의 길이를 나타내는 두 정수 $n$ 과 $k$ ($1 \le n \le 20\,000$, $1 \le k \le 100$) 가 공백 하나로 구분되어 주어진다.

둘째 줄에 수열 $(a_i)$ 가 주어진다. 즉, $n$ 개의 정수 $a_i$ ($1 \le a_i \le 1\,000\,000$) 가 공백 하나로 구분되어 주어진다.

셋째 줄에 단조성 표식 $(s_j)$ 가 주어진다. 즉, 각각 $<$, $>$, $=$ 중 하나인 $k$ 개의 기호 $s_j$ 가 공백 하나로 구분되어 주어진다.

첫째 줄에 수열 $a_1, a_2, \ldots, a_n$ 의 부분 수열 중에서 표식 $s_1, s_2, \ldots, s_k$ 를 실현하는 것의 최대 길이 $m$ 을 정수 하나로 출력한다.