Problem Background

The overachiever has arrived at his good friend bj12z_jiasiyuan's farm, planning to spend a night there. However, while watching the news, they received unfortunate information that a meteor shower is about to strike...

Problem Description

bj12z_jiasiyuan's farm has $n$ barns, numbered from $1$ to $n$. The defense value of the $i$-th barn is $a_i$.

The meteor shower will arrive in $t$ seconds. During the meteor shower, $m$ meteors will strike the barns, with the $i$-th meteor hitting the $x_i$-th barn. When a meteor hits a barn, the barn's defense value will decrease by 2 points. When a barn's defense value $\leq 0$, the barn will be destroyed.

bj12z_jiasiyuan has many supplies, each of which can increase the defense value of a barn by 1 point. Fortunately, the overachiever can teleport from one barn to another (teleportation does not take any time), using supplies to increase the defense value of the barns. Each supply takes 1 second to apply.

The overachiever has only $t$ seconds to go out and apply supplies, and he wants to minimize the number of destroyed barns. Please output the number of barns protected under the optimal strategy.

Input Format

This problem contains multiple test cases within a single test point.

The first line contains an integer $T$, representing the number of test cases. The next $T$ groups of data, each containing three lines.

The first line of each group contains three integers $n, t, m$, representing the number of barns, the time available for the overachiever to apply supplies, and the number of meteors, respectively.
The next line contains $n$ integers $a_1, a_2, \cdots, a_n$, representing the defense value of the $i$-th barn.
The last line contains $m$ integers $x_1, x_2, \cdots, x_m$, representing that the $i$-th meteor will strike the $x_i$-th barn.

Output Format

Output $T$ lines, each containing an integer, representing the number of barns protected under the optimal strategy for each test case.

Sample Input and Output

Input Sample #1

1
4 3 5
2 1 3 5
3 1 2 4 3

Output Sample #1

3

Input Sample #2

4
3 4 2
5 2 4
2 1
3 2 20
6 6 6
1 3 3 1 2 1 1 1 2 2 2 1 1 3 1 2 2 3 3 1
2 0 2
1 2
1 1
5 3 12
4 5797 2 1 1
5 4 3 2 4 4 5 5 5 5 1 1

Output Sample #2

3
0
1
3

Notes

Sample 1 Explanation

One optimal supply strategy is to supply the 1st barn with 1 point of defense and the 2nd barn with 2 points of defense.

In this case, the defense values of the barns change as follows, where blue numbers represent initial defense values, green numbers represent supplies, and red numbers represent meteor strikes:

• 1st: ${\color{blue} 2} + {\color{green}1} - {\color{red}2} = 1$;
• 2nd: ${\color{blue} 1} + {\color{green}2} - {\color{red}2} = 1$;
• 3rd: ${\color{blue} 3} - {\color{red}2} - {\color{red}2} = -1$;
• 4th: ${\color{blue} 5} - {\color{red}2} = 3$.

Only the 3rd barn is destroyed, protecting three barns.

Data Size and Constraints

For $100\%$ of the data, $1\leq x_i \leq n\leq 5 \times 10^3$, $1\leq m\leq 10^6$, $0\leq t\leq 10^6$, $1\leq a_i \leq 10^6$, $1 \leq T \leq 5 \times 10^3$.
The sum of $n$ across all test cases within a single test point does not exceed $5 \times 10^4$, and the sum of $m$ across all test cases does not exceed $3 \times 10^6$.

见题面 Input 部分

见题面 Output 部分