Задача B. Лотерея

Автор:Известная   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Недавно организация ACM (Association Consuming Money) объявила о проведении лотереи по новой схеме. Участник, купив билет, должен написать в нем последовательность чисел некоторой длины. При розыгрыше случайным образом выбирается другая последовательность, причем ее элементы могут повторяться.

Общая подпоследовательность определяется как последовательность чисел, которую можно получить вычеркиванием чисел как из первой последовательности, так и из второй.

Сумма выигрыша участника определяется через размер наибольшей общей подпоследовательности чисел в его билете и в розыгрыше. Поэтому, чтобы исключить возможность человеческой ошибки в таком важном вопросе, как подсчет денег, нужно написать программу, которая будет это делать автоматически.

Формат входного файла

Первая строка входного файла содержит числа N и M — длины первой и второй последовательностей.

Вторая строка содержит N целых чисел ai разделенных пробелами — последовательность участника.

Третья строка содержит M целых чисел bi разделенных пробелами — последовательность, полученная при розыгрыше.

Формат выходного файла

В выходной файл выведите длину наибольшей общей подпоследовательности.

Ограничения

1 ≤ N, M ≤ 1000

0 ≤ ai, bi ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 3
1 2 3 4 5
2 4 4
2

0.037s 0.009s 15