粉红士兵以他们的中心画了 $$$n$$$ 圆圈 $$$x$$$ 轴上的 飞机的 。此外,他们还告诉我们 半径之和正好是 $$$m$$$$$$^{\text{*}}$$$。
请求整数点数 内部或边界上 至少一圈。正式地,该问题定义如下。
给定一个整数序列 $$$x_1,x_2,\ldots,x_n$$$ 和一个正整数序列 $$$r_1,r_2,\ldots,r_n$$$,其中已知 $$$\sum_{i=1}^n r_i = m$$$。
您必须计算满足以下条件的整数对 $$$(x,y)$$$ 的数量。
- 存在一个索引 $$$i$$$ 使得 $$$(x-x_i)^2 + y^2 \le r_i^2$$$ ($$$1 \le i \le n$$$)。
$$$^{\text{*}}$$$这些信息真的有用吗?别问我;我真的不知道。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le m \le 2\cdot 10^5$$$)。
每个测试用例的第二行包含 $$$x_1,x_2,\ldots,x_n$$$ — 圆心 ($$$-10^9 \le x_i \le 10^9$$$)。
每个测试用例的第三行包含 $$$r_1,r_2,\ldots,r_n$$$ - 圆的半径 ($$$1 \le r_i$$$, $$$\sum_{i=1}^n r_i = m$$$)。
保证 所有测试用例 $$$m$$$ 的总和 不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,在单独的行上输出满足条件的整数点数。
示例
输入复制
42 30 01 22 30 21 23 30 2 51 1 14 80 5 10 152 2 2 2
输出复制
13 16 14 52
注意
在第一个测试用例中,$$$r_1=1$$$ 的圆完全位于 $$$r_2=2$$$ 的圆内。因此,你只需计算后者内部的整数点数即可。有 $$$13$$$ 整数点使得 $$$x^2+y^2 \le 2^2$$$,所以答案是 $$$13$$$。
在第二个测试用例中,$$$r_1=1$$$ 的圆不完全位于 $$$r_2=2$$$ 的圆内。还有 $$$3$$$ 个额外点位于第一个圆内,但不在第二个圆内,因此答案为 $$$3+13=16$$$。