曼哈顿多焦点椭圆

题目描述

在二维平面上给定 $N$ 个点 $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$，以及一个非负整数 $D$。

求满足 $\displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D$ 的整数对 $(x, y)$ 的个数。

输入格式

输入按以下格式从标准输入给出：

$N$ $D$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

输出格式

输出答案。

样例

2 3
0 0
1 0

8

下图直观展示了样例 1 的输入与答案。蓝色点表示输入的点。满足题述条件的点共有 8 个（蓝色点和红色点合计）。

2 0
0 0
2 0

0

6 100
9 -6
10 -1
2 10
-1 7
-7 5
-1 -4

419

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq D \leq 10^6$
• $-10^6 \leq x_i, y_i \leq 10^6$
• 对于 $i \neq j$，有 $(x_i, y_i) \neq (x_j, y_j)$。
• 所有输入值均为整数。