Bài 6. Dãy con chung dài nhất của hai dãy số

Mô tả

Cho hai dãy số nguyên:

• a1, a2, ..., an
• b1, b2, ..., bm

Hãy tìm độ dài dãy con chung dài nhất của hai dãy.

Input

• Dòng 1 chứa hai số nguyên n m.
• Dòng 2 chứa n số nguyên a1, a2, ..., an.
• Dòng 3 chứa m số nguyên b1, b2, ..., bm.

Output

• In ra độ dài LCS của hai dãy số.

Ràng buộc

• 1 <= n, m <= 1000
• |ai|, |bi| <= 10^9

Subtask

• Subtask 1 (30%): n, m <= 100
• Subtask 2 (70%): Không có ràng buộc gì thêm.

Ví dụ

Input

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

Output

5

Giải thích ví dụ

Một LCS là 3 4 1 2 3.