CF2074D Counting Points

The pink soldiers drew $ n $ circles with their center on the $ x $ -axis of the plane. Also, they have told that the sum of radii is exactly $ m $ $ ^{\text{∗}} $ . Please find the number of integer points inside or on the border of at least one circle. Formally, the problem is defined as follows. You are given an integer sequence $ x_1,x_2,\ldots,x_n $ and a positive integer sequence $ r_1,r_2,\ldots,r_n $ , where it is known that $ \sum_{i=1}^n r_i = m $ . You must count the number of integer pairs $ (x,y) $ that satisfy the following condition. - There exists an index $ i $ such that $ (x-x_i)^2 + y^2 \le r_i^2 $ ( $ 1 \le i \le n $ ). $ ^{\text{∗}} $ Is this information really useful? Don't ask me; I don't really know.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le m \le 2\cdot 10^5 $ ). The second line of each test case contains $ x_1,x_2,\ldots,x_n $ — the centers of the circles ( $ -10^9 \le x_i \le 10^9 $ ). The third line of each test case contains $ r_1,r_2,\ldots,r_n $ — the radii of the circles ( $ 1 \le r_i $ , $ \sum_{i=1}^n r_i = m $ ). It is guaranteed that the sum of $ m $ over all test cases does not exceed $ 2\cdot 10^5 $ .

For each test case, output the number of integer points satisfying the condition on a separate line.

On the first test case, the circle with $ r_1=1 $ is completely inside the circle with $ r_2=2 $ . Therefore, you only have to count the number of integer points inside the latter. There are $ 13 $ integer points such that $ x^2+y^2 \le 2^2 $ , so the answer is $ 13 $ . On the second test case, the circle with $ r_1=1 $ is not completely inside the circle with $ r_2=2 $ . There are $ 3 $ additional points that are inside the first circle but not inside the second circle, so the answer is $ 3+13=16 $ .