分数: 475 点
问题陈述
你被给予 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.
约束
- 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.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N D x_1 y_1 x_2 y_2 \vdots x_N y_N
输出
打印答案。
示例输入 1
2 3 0 0 1 0
示例输出 1
8
下图可视化了 Sample 的输入和答案 1。蓝点代表输入。蓝点和红点共八个,满足语句中的条件。

示例输入 2
2 0 0 0 2 0
示例输出 2
0
示例输入 3
6 100 9 -6 10 -1 2 10 -1 7 -7 5 -1 -4
示例输出 3
419