CF2074D.Counting Points

粉色士兵们在平面上绘制了 $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$。

对于每个测试用例，在单独一行中输出满足条件的整数点数量。

在第一个测试用例中，半径为 $r_1=1$ 的圆完全包含在半径为 $r_2=2$ 的圆内部。因此只需统计后者内部的整数点数量。满足 $x^2 + y^2 \le 2^2$ 的整数点共有 $13$ 个，因此答案为 $13$。

在第二个测试用例中，半径为 $r_1=1$ 的圆未完全包含在半径为 $r_2=2$ 的圆内部。存在 $3$ 个额外整数点位于第一个圆内但不在第二个圆内，因此答案为 $3+13=16$。

翻译由 DeepSeek R1 完成