题目描述

给你一个二维平面上的 $N$ 点 $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$ 和一个非负整数 $D$ 。

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

输入格式

输入内容由标准输入法提供，格式如下

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

输出格式

打印答案。

2 3
0 0
1 0

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$
• $(x_i, y_i) \neq (x_j, y_j)$ 为 $i \neq j$ 。
• 所有输入值均为整数。