Common scores P95498


Statement
 

pdf   zip

html

Two friends, Arthur and Bob, are playing computer games, and they have decided to store their scores. When they stop playing, Arthur and Bob want to determine the length of the maximum subsequence of scores that they have in common.

For instance, if the scores of Arthur are [8, 12, 6, 9, 2], and those of Bob are [12, 6, 8, 2], then the maximum subsequence that they have in common is [12, 6, 2], which has length 3. Note that a subsequence does not have to be made up of consecutive elements, but we must preserve the order of the scores.

Input

Input consists of several cases. Each case begins with two numbers 0≤ M≤ 1000 and 0≤ N≤ 1000, representing the length of the subsequences of Arthur and Bob, respectively. Follow the M numbers of Arthur, and the N numbers of Bob. All the numbers are natural.

Output

For every case, print the length of the longest common subsequence.

Public test cases

  • Input

    5 4
8 12 6 9 2
12 6 8 2
7 7
8 13 16 7 12 9 5
16 7 9 5 8 13 16
15 12
11 9 12 6 2 6 12 19 2 7 1 16 12 15 2
9 6 18 6 12 17 19 8 7 12 3 15

    Output

    3
4
8
    • Information
    Author
    Anders Jonsson
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++ Python
    User solutions
    C++ Python