Cho số nguyên dương \(n\). Một dãy \(a\) được gọi là siêu hoán vị hệ \(k\) nếu mỗi số nguyên \(1, 2, ..., n\) xuất hiện đúng \(k\) lần. Ví dụ, \(n = 3\) và \(k = 2\) thì \([1, 2, 2, 3, 1, 3]\) là một siêu hoán vị.

Cho \(a\) va \(b\) là hai siêu hoán vị hệ \(k\). Hãy tìm dãy con chung dài nhất của chúng. Lưu ý rằng:

• Dãy \(c\) được gọi là dãy con của \(a\) nếu \(c\) có thể nhận được bằng cách bỏ đi vài số trong \(a\) và giữ nguyên thứ tự các số còn lại. Ví dụ, \([1, 3]\) là dãy con của \([1, 2, 3]\) và \([3, 2]\) thì không phải.
• Dãy \(c\) được gọi là dãy con chung của \(a\) và \(b\), nếu \(c\) là dãy con của \(a\) và \(c\) là dãy con của \(b\).

Input

• Dòng đầu tiên chứa số hai nguyên dương \(n, k \ (1 \leq n \leq 10^5, 1 \leq k \leq 5)\).
• Dòng thứ hai chứa \(nk\) số nguyên \(a_1, a_2, ..., a_{nk} \ (1 \leq a_i \leq n)\) và mỗi số từ \(1\) đến \(n\) xuất hiện đúng \(k\) lần.
• Dòng thứ hai chứa \(nk\) số nguyên \(b_1, b_2, ..., b_{nk} \ (1 \leq b_i \leq n)\) và mỗi số từ \(1\) đến \(n\) xuất hiện đúng \(k\) lần.

Output

• In ra một số nguyên dương là độ dài của dãy con chung dài nhất.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 1000\)
• Subtask \(2\) (\(40\%\) số điểm): \(k = 1\)
• Subtask \(3\) (\(40\%\) số điểm): không có điều kiện gì thêm.

Example

3 2
1 2 3 1 2 3
2 1 3 3 2 1

3

3 1
1 2 3
3 2 1   

1