시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB1000.000%

문제

На собеседовании при поступлении на работу в компанию Sasnart кандидатам предлагается решить задачу о наибольшей общей возрастающей подпоследовательности двух последовательностей чисел.

Суть задачи сводится к следующему: из последовательности чисел $a_i$ необходимо выделить подпоследовательность $a_{i_k}$ такую, что она:

  • возрастает, т. е. $\forall{k}:a_{i_k} < a_{i_{k+1}}$
  • является подпоследовательностью последовательности $b_i$
  • имеет длину, не меньшую, чем все последовательности, обладающие предыдущими двумя свойствами

Вам же, для проверки правильности решения кандидатами этой задачи, необходимо научиться вычислять хотя бы длину такой подпоследовательности.

입력

В первой строке входного файла даны два целых числа $n$ и $m$ ($1 \le n, m \le 5,000$) --- длины последовательностей $a_i$ и $b_i$. Вторая и третья строки содержат, соответственно, по $n$ и $m$ натуральных чисел, не превосходящих $10,000$, --- сами последовательности.

출력

В выходной файл выведите единственное целое число --- длину последовательности, обладающей описанными свойствами.

예제 입력 1

6 5
2 3 1 4 6 5
1 2 5 4 6

예제 출력 1

3