D. Подсчет точек
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Розовые солдаты нарисовали $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите количество точек с целочисленными координатами, удовлетворяющих условию, на отдельной строке.

Пример
Входные данные
4
2 3
0 0
1 2
2 3
0 2
1 2
3 3
0 2 5
1 1 1
4 8
0 5 10 15
2 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$$$.