{"code":"lovepair","name":"Cặp số \"yêu thương\"","description":"Cho một mảng gồm $n$ số nguyên $a_1,a_2,...a_n$, chúng ta gọi $\\left\\{a_i,a_j\\right\\}$ là cặp số \"**yêu thương**\" của mảng đã cho nếu $i\\ne j$ và $a_i+a_j$ là số nguyên tố. \r\n\r\nCho số nguyên không âm $k$.\r\n\r\n**Yêu cầu:** Chọn ra $m$ cặp \"**yêu thương**\" $p_1,p_2,...,p_m$ từ mảng trên thỏa mãn những điều kiện sau: \r\n\r\n + $m\\le k$\r\n\r\n + $S=|p_1\\cup p_2\\cup...\\cup p_m|$ đạt giá trị lớn nhất. Và xuất kết quả $S $ này ra màn hình.\r\n\r\n

Input

\r\n\r\n+ Dòng thứ nhất chứa số nguyên $T(1\\le T\\le 20)$ - Thể hiện số testcase\r\n\r\n+ Dòng thứ hai chứa hai số nguyên $n,k(1\\le n\\le 3000; 0\\le k\\le \\frac{n(n-1)}{2})$\r\n\r\n+ Dòng thứ ba chứa $n$ số nguyên $a_1,a_2,...,a_n$ với $1\\le a_i\\le 10^6$\r\n\r\n

Output

\r\n\r\n+ In ra giá trị $S$ cần tìm.\r\n\r\n

Scoring

\r\n\r\n+ Subtask $1$ ($20\\%$ số điểm): $1\\le n\\le 10$\r\n\r\n+ Subtask $2$ ($80\\%$ số điểm): $1\\le n\\le 3000$\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 1\r\n 4 2 \r\n 5 4 3 2\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 4\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Ở ví dụ 1 ta tìm được hai cặp \"**yêu thương**\": $p_1=\\left\\{a_1,a_4\\right\\}=\\left\\{5,2\\right\\};p_2=\\left\\{a_2,a_3\\right\\}=\\left\\{4,3\\right\\}$\r\n\r\n Do đó $S=|p_1\\cup p_2|=4$. (vì $p_1\\cup p_2 =\\left\\{5,2,3,4\\right\\}$)\r\n\r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 1\r\n 3 2\r\n 1 1 2\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 2\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Ở ví dụ 2 ta tìm được hai cặp \"**yêu thương**\": $p_1=\\left\\{a_1,a_2\\right\\}=\\left\\{1,1\\right\\};p_2=\\left\\{a_2,a_3\\right\\}=\\left\\{1,2\\right\\}$\r\n\r\n Do đó $S=|p_1\\cup p_2|=2$. (vì $p_1\\cup p_2 =\\left\\{1,2\\right\\}$)","points":600.0,"partial":false,"time_limit":2.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}}