{"code":"lcsperm","name":"Dãy con chung hoán vị","description":"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ị. \r\n\r\nCho $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:\r\n\r\n+ 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.\r\n+ 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$.\r\n\r\n

Input

\r\n\r\n+ 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)$.\r\n+ 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.\r\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.\r\n\r\n

Output

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

Scoring

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3 2\r\n 1 2 3 1 2 3\r\n 2 1 3 3 2 1\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 3\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n + Trong ví dụ 1, dãy con chung dài nhất là $[2, 3, 3]$\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3 1\r\n 1 2 3\r\n 3 2 1 \r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 1\r\n ```","points":450.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}