This page is still under construction.

Parts of this page are still being built. What you see may change.

Card Game is Fun

Time limit1sMemory limit128 MB

Summary
Anna may delete arbitrary cards from her sequence and Bruno may trim cards from the top and bottom of his; find the longest common subarray obtainable.
Level

Medium6 of 10

Topics
Dynamic programming, Array, Prefix sum, String matching
Solved
No attempts yet

Problem

There are many cards, each showing one integer from 11 to 10001000. Anna and Bruno play the following game with these cards.

Anna holds a pile of AA cards and Bruno holds a pile of BB cards. Anna discards any number of cards (possibly 00) from her AA cards to form a new pile. Bruno discards some number of cards (possibly 00) from the top of his pile of BB cards and some number of cards (possibly 00) from the bottom to form a new pile. When discarding, the order of the remaining cards is never changed.

If the two piles formed this way are identical, the number of cards in one of the piles becomes the score of both players. Here, the two piles are identical if they contain the same number of cards nn and, for every position, the integer on the ii-th card from the top (1≤i≤n1 \le i \le n) is the same in both piles.

For example, suppose Anna holds 5 cards showing 1,2,3,4,51, 2, 3, 4, 5 from top to bottom, and Bruno holds 4 cards showing 3,1,4,13, 1, 4, 1 from top to bottom. If Anna discards the cards 2,3,52, 3, 5 and Bruno discards the top 33 and the bottom 11, both piles become 1,41, 4 from the top and are identical. The remaining pile has 2 cards, so both players score 22.

We want to find the maximum possible score. Given the information about the piles held by Anna and Bruno, write a program that computes the maximum score.

Input

Read the following data from standard input.

  • The first line contains two integers AA and BB, separated by a space.
  • The second line contains AA integers separated by spaces; the ii-th integer (1≤i≤A1 \le i \le A) is the integer written on the ii-th card from the top of Anna's pile.
  • The third line contains BB integers separated by spaces; the jj-th integer (1≤j≤B1 \le j \le B) is the integer written on the jj-th card from the top of Bruno's pile.

Constraints

  • 1≤A≤50001 \le A \le 5000
  • 1≤B≤50001 \le B \le 5000
  • Every integer written on a card is between 11 and 10001000, inclusive.

Output

Print the maximum score as a single integer on one line.

Examples2

  1. Example 1

    Input
    5 4
    1 2 3 4 5
    3 1 4 1
    
    Expected output
    2
    
  2. Example 2

    Input
    6 5
    4 1 5 2 3 4
    4 5 4 2 3
    
    Expected output
    3