CF1494C 1D Sokoban

C. 1D Sokoban

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are playing a game similar to Sokoban on an infinite number line. The game is discrete, so you only consider integer positions on the line.

You start on a position 00. There are nn boxes, the ii-th box is on a position aiai. All positions of the boxes are distinct. There are also mm special positions, the jj-th position is bjbj. All the special positions are also distinct.

In one move you can go one position to the left or to the right. If there is a box in the direction of your move, then you push the box to the next position in that direction. If the next position is taken by another box, then that box is also pushed to the next position, and so on. You can't go through the boxes. You can't pull the boxes towards you.

You are allowed to perform any number of moves (possibly, zero). Your goal is to place as many boxes on special positions as possible. Note that some boxes can be initially placed on special positions.

Input

The first line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of testcases.

Then descriptions of tt testcases follow.

The first line of each testcase contains two integers nn and mm (1≤n,m≤2⋅1051≤n,m≤2⋅105) — the number of boxes and the number of special positions, respectively.

The second line of each testcase contains nn distinct integers in the increasing order a1,a2,…,ana1,a2,…,an (−109≤a1<a2<⋯<an≤109−109≤a1<a2<⋯<an≤109; ai≠0ai≠0) — the initial positions of the boxes.

The third line of each testcase contains mm distinct integers in the increasing order b1,b2,…,bmb1,b2,…,bm (−109≤b1<b2<⋯<bm≤109−109≤b1<b2<⋯<bm≤109; bi≠0bi≠0) — the special positions.

The sum of nn over all testcases doesn't exceed 2⋅1052⋅105. The sum of mm over all testcases doesn't exceed 2⋅1052⋅105.

Output

For each testcase print a single integer — the maximum number of boxes that can be placed on special positions.

Example

input

Copy

5
5 6
-1 1 5 11 15
-4 -3 -2 6 7 15
2 2
-1 1
-1000000000 1000000000
2 2
-1000000000 1000000000
-1 1
3 5
-1 1 2
-2 -1 1 2 5
2 1
1 2
10

output

Copy

4
2
0
3
1

Note

In the first testcase you can go 55 to the right: the box on position 11 gets pushed to position 66 and the box on position 55 gets pushed to position 77. Then you can go 66 to the left to end up on position −1−1 and push a box to −2−2. At the end, the boxes are on positions [−2,6,7,11,15][−2,6,7,11,15], respectively. Among them positions [−2,6,7,15][−2,6,7,15] are special, thus, the answer is 44.

In the second testcase you can push the box from −1−1 to −109−109, then the box from 11 to 109109 and obtain the answer 22.

The third testcase showcases that you are not allowed to pull the boxes, thus, you can't bring them closer to special positions.

In the fourth testcase all the boxes are already on special positions, so you can do nothing and still obtain the answer 33.

In the fifth testcase there are fewer special positions than boxes. You can move either 88 or 99 to the right to have some box on position 1010.

#include <bits/stdc++.h>
using namespace std;

const int N = 300001;
map<int, int> mp;
int input[N], inask[N];
int a[N], b[N];

int solve(int lena, int lenb){
    int count = 0;
    mp.clear();
    for(int i = 1; i <= lena; i++){
        mp[a[i]] = 1;
    }
    for(int i = 1; i <= lenb; i++)
        if(mp[b[i]]) count++;
    int res = count;
    int ans = res;
    for(int i = 1; i <= lenb; i++){
        if(mp[b[i]]){
            res--;
            continue;
        }
        int pp = upper_bound(a+1, a+1+lena, b[i])-a-1; // pp表示连在一起的箱子有多少个
        int qq = upper_bound(b+1, b+lenb+1, b[i]-pp)-b; // qq表示在一坨箱子最后一个前面的特殊点的位置序号（第几个）
        ans = max(ans, res+i-qq+1);
    }
    return ans;
}

int main()
{
    int T;
    cin >> T;
    while(T--){
        int n, m;
        int lena = 0, lenb = 0;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++){
            scanf("%d", &input[i]);
            if(input[i] >= 0)
                a[++lena] = input[i];
        }
        for(int i = 1; i <= m; i++){
            scanf("%d", &inask[i]);
            if(inask[i] >= 0)
                b[++lenb] = inask[i];
        }
        int ans = solve(lena, lenb);
        lena = lenb = 0;
        for(int i = n; i >= 1; i--){
            if(input[i] < 0) a[++lena] = -input[i];
        }
        for(int i=m; i>=1; i--){
            if(inask[i] < 0) b[++lenb] = -inask[i];
        }
        ans += solve(lena, lenb);

        cout << ans << endl;

    }

    return 0;
}