Monotonicity

For an integer sequence $a_1, a_2, \ldots, a_n$ we define its monotonicity scheme as the sequence $s_1, s_2, \ldots, s_{n-1}$ of symbols $<$, $>$, or $=$. The symbol $s_i$ describes the relation between $a_i$ and $a_{i+1}$. For example, the monotonicity scheme of the sequence $2, 4, 3, 3, 5, 3$ is $<, >, =, <, >$.

We say that an integer sequence $b_1, b_2, \ldots, b_{n+1}$ with monotonicity scheme $s_1, s_2, \ldots, s_n$ realizes another monotonicity scheme $s'_1, s'_2, \ldots, s'_k$ if for every $i = 1, 2, \ldots, n$ it holds that $s_i = s'_{((i-1) \bmod k) + 1}$. In other words, the sequence $s_1, s_2, \ldots, s_n$ can be obtained by repeating the sequence $s'_1, s'_2, \ldots, s'_k$ and removing an appropriate suffix from that repetition. For example, the sequence $2, 4, 3, 3, 5, 3$ realizes every one of the following schemes:

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

as well as many others.

You are given an integer sequence $a_1, a_2, \ldots, a_n$ and a monotonicity scheme $s_1, s_2, \ldots, s_k$. Find the longest subsequence $a_{i_1}, a_{i_2}, \ldots, a_{i_m}$ (with $1 \le i_1 < i_2 < \cdots < i_m \le n$) of the given sequence that realizes the given scheme.

The first line contains two integers $n$ and $k$ ($1 \le n \le 20\,000$, $1 \le k \le 100$), separated by a single space, denoting the lengths of the sequence $(a_i)$ and of the monotonicity scheme $(s_j)$ respectively.

The second line contains the sequence $(a_i)$: $n$ integers $a_i$ separated by single spaces ($1 \le a_i \le 1\,000\,000$).

The third line contains the monotonicity scheme $(s_j)$: $k$ symbols $s_j$, each one of $<$, $>$, or $=$, separated by single spaces.

Print a single integer $m$: the maximum length of a subsequence of $a_1, a_2, \ldots, a_n$ that realizes the scheme $s_1, s_2, \ldots, s_k$.