本题需要文件读写

文件 IO 为：输入文件 stamp.in，输出文件 stamp.out。请使用上述文件名读入和输出。

题目描述

公园正在举行环湖集章活动。湖岸是一条周长为 $L$ 米的环形步道，步道上设有 $N$ 个集章点，依次编号为 $1, 2, \dots, N$。从活动起点沿顺时针方向行走 $X_i$ 米，就会到达第 $i$ 个集章点。输入按顺时针顺序给出各点的位置，即 $X_1 < X_2 < \dots < X_N$。

活动在时刻 $0$ 开始，小林此时位于起点。他每秒行走 $1$ 米，可以沿顺时针或逆时针方向行走，也可以在途中改变方向，改变方向的次数不限。

第 $i$ 个集章点只在活动开始后的前 $T_i$ 秒内提供印章。如果小林到达该点的时刻不晚于 $T_i$，就可以取得该点的印章；恰好在时刻 $T_i$ 到达也可以。盖章不花费时间。每个集章点提供的印章各不相同，同一点的印章至多计入一次。

已经停止提供印章的集章点仍然可以经过。小林不需要回到起点，也没有必须经过所有集章点的要求。请问他最多能取得多少枚不同的印章？

输入格式

第一行包含一个整数 $T$，表示相互独立的活动组数。

接下来依次给出 $T$ 组数据，每组格式如下：

• 第一行包含两个整数 $N, L$，分别表示集章点的数量和步道的周长。
• 第二行包含 $N$ 个整数 $X_1, X_2, \dots, X_N$，表示各集章点的位置。
• 第三行包含 $N$ 个整数 $T_1, T_2, \dots, T_N$，表示各集章点停止提供印章的时刻。

输出格式

输出 $T$ 行，每行一个整数，依次表示对应一组活动中小林最多能取得的不同印章数量。每组都重新从该组的起点、时刻 $0$ 出发，前一组的行走与印章不会影响后一组。

样例输入 1

1
6 25
3 4 7 17 21 23
11 7 17 10 8 10

样例输出 1

4

说明

样例解释

小林可以按以下方式行走：

1. 从起点逆时针行走 $2$ 米，时刻 $2$ 到达第 $6$ 个集章点，取得印章。
2. 继续逆时针行走 $2$ 米，时刻 $4$ 到达第 $5$ 个集章点，取得印章。
3. 改为顺时针行走 $7$ 米，时刻 $11$ 到达第 $1$ 个集章点，恰好赶上截止时刻，取得印章。
4. 继续顺时针行走 $1$ 米，时刻 $12$ 到达第 $2$ 个集章点。此时该点已经停止提供印章，但仍可经过。
5. 再顺时针行走 $3$ 米，时刻 $15$ 到达第 $3$ 个集章点，取得印章。

这样共取得 $4$ 枚不同的印章。不存在取得 $5$ 枚或更多不同印章的行走方案，因此答案为 $4$。

其它样例说明

• 样例 2：见选手目录下的 stamp/stamp2.in 与 stamp/stamp2.ans。该样例满足测试点 $1$ 的约束。
• 样例 3：见选手目录下的 stamp/stamp3.in 与 stamp/stamp3.ans。该样例满足测试点 $2 \sim 3$ 的约束。
• 样例 4：见选手目录下的 stamp/stamp4.in 与 stamp/stamp4.ans。该样例满足测试点 $4 \sim 5$ 的约束。
• 样例 5：见选手目录下的 stamp/stamp5.in 与 stamp/stamp5.ans。该样例满足完整数据范围。
• 样例 6：见选手目录下的 stamp/stamp6.in 与 stamp/stamp6.ans。该样例满足完整数据范围。
• 样例 7：见选手目录下的 stamp/stamp7.in 与 stamp/stamp7.ans。该样例满足测试点 $4 \sim 5$ 的约束。

数据范围

对于所有测试数据，均有 $1 \le T \le 20$，同一输入文件内各组 $N$ 之和 $\sum N \le 600$。每组数据均满足：

• $1 \le N \le 200$，$2 \le L \le 10^9$。
• $1 \le X_i < L$，且 $X_i < X_{i+1}$。
• $0 \le T_i \le 10^9$。
• 所有输入均为整数。

各测试点的附加约束如下表所示：

点击下载大样例