Cặp số "yêu thương"

Tác giả:

Dạng bài

Điểm: 600 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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ố.

Cho số nguyên không âm $k$.

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:

$m\le k$
$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.

Input

Dòng thứ nhất chứa số nguyên $T(1\le T\le 20)$ - Thể hiện số testcase
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})$
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$

Output

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

Scoring

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

Example

Test 1

Input

1
4 2 
5 4 3 2

Output

Note

Ở 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\}$

Do đó $S=|p_1\cup p_2|=4$. (vì $p_1\cup p_2 =\left\{5,2,3,4\right\}$)

Test 2

Input

1
3 2
1 1 2

Output

Note

Ở 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\}$

Do đó $S=|p_1\cup p_2|=2$. (vì $p_1\cup p_2 =\left\{1,2\right\}$)

Bình luận

Không có bình luận nào.