[Login|Register]
Problems

Status

Rank

Problem 1120
Greatest Common Increasing Subsequence
Time Limit: 1000ms
Memory Limit: 65536kb
Description

As a ACM/ICPC contestant, you probably have heard about Greatest Common Subsequence. And the problem here is an advanced version. We want you to calculate the length of a Greatest Common Increasing Subsequence.

A Greatest Common Increasing Subsequence is a common subsequence of two sequences keeping an ascending order. For instance, let A = 1, 4, 2, 5, -12; B = 1, 2, 4,-12. Both sequence 1, 2 or 1, 4, -12 are common subsequences but only 1, 2 is in ascending order. And it's the longest one.

Input

The input contains multiple test cases.

Each test case starts with 2 integers N and M (1 <= N, M <= 500), indicating the length of the two sequences. Then follows with two lines of numbers indicating the sequences (each number in range (-231, 231 ) ) A line with 0 0 terminates the input.

Output
For each test case, output the length of the Greatest Common Increasing Subsequence in a single line.
Sample Input
5 4
1 4 2 5 -12
-12 1 2 4
0 0
Sample Output
2
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.8ms with 1 query(s).