E. 步道

注意 TLE : 8 sec / Input size 25MB sprout

題目敘述

$Allen$所生活的地方有很多座山，這些山的高度可以構造一個高度的序列，這些序列有一些相對關係，假若高度序列有$N$個數字，分別為$2,4,3,3,5,3$，那則會有$N − 1$個相鄰關係，使用符號$>,<,=$來表示，如上範例的相鄰關係表示為$<,>,=,<,>$。

我們定義一個健行方案，是一個高度序列$b1,b2,b3...bn$與相鄰關係 $s1,s2,s3...sk$的組合，如果 $k<n-1$ 的話，我們把相鄰關係循環使用，以滿足長度，即變成$s1,s2,s3...sk,s1,s2...$使得關係序列可以覆蓋整個高度序列。如果 $k>n-1$，則去除超長度的部分即可，一個合法的健行方案，要使得高度序列的相鄰關係滿足給定的相鄰關係，比如說高度序列$2,4,3,3,5,3$可以與下關係組成合法的搭配：

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

今天 $Allen$ 給你一個高度序列以及指定的相鄰關係，你能不能找到一個最長的子序列，使得該序列與指定的關係是合法的健行方案?

輸入說明

有多筆測資，每筆測資第一行包含兩個數字，$N K$，表示高度序列長度為$N$，關係序列長度為 $K$，接下下一行來有$N$個整數以空白隔開，表示高度序列。再下一行有$K$ 個字元以空白隔開，表示要求的關係序列。保證$0 < N , K \leq 200000$數字皆可用 32bits int 表達，關係序列以$<=>$表達

輸出說明

對於每筆測資輸出一行，為滿足要求關係序列的高度序列最長長度為何。

範例輸入

7 3
2 4 3 1 3 5 3
< > =

範例輸出

Source

Judge Setting

run-time limit: 8000 ms
memory limit: 6553600 byte
測資數量: 0