题目描述

古代边防用烽火传递军情。一条海岸线上有 $n$ 座烽火台，第 $i$ 座烽火台的坐标为 $x_i$，信号强度为 $b_i$。所有烽火台的坐标互不相同，输入已按坐标严格递增的顺序给出。

为了统筹调度，守将决定新建一座中央烽火台。它的位置必须从给定的 $m$ 个候选点 $y_1 < y_2 < \cdots < y_m$ 中选取。中央烽火台的覆盖半径为 $R$（$R$ 是非负整数），凡是满足 $|x_i - y_j| \le R$ 的烽火台 $i$ 都能与它建立通信。

我们称候选点 $y_j$ 的通信收益为所有能与它建立通信的烽火台的信号强度之和。

请你求出收益最大的候选点，输出该收益的值以及对应的坐标。如果存在多个候选点的收益相同，输出其中坐标最小的那个。

输入格式

第一行三个整数 $n, m, R$。

接下来 $n$ 行，每行两个整数 $x_i, b_i$，描述一座烽火台。

接下来 $m$ 行，每行一个整数 $y_j$，描述一个候选点。

输出格式

一行两个整数，用一个空格隔开：最大的通信收益，以及取到该收益的候选点坐标（收益并列时取坐标最小者）。

3 2 5
1 10
10 20
20 30
8
15

50 15

3 3 2
0 5
10 5
20 5
1
11
19

5 1

2 3 1
-100 5
100 6
-50
0
50

0 -50

【样例 1 解释】

候选点 $y=8$：只有 $|10-8| = 2 \le 5$，故只覆盖第 $2$ 座烽火台，收益为 $20$。

候选点 $y=15$：$|10-15| = 5 \le 5$ 且 $|20-15| = 5 \le 5$，覆盖第 $2,3$ 座烽火台，收益为 $20+30 = 50$。

两者取大，输出 50 15。

【样例 2 解释】

$R = 2$。候选点 $1$ 覆盖坐标 $0$ 的烽火台，收益 $5$；候选点 $11$ 覆盖坐标 $10$ 的烽火台，收益 $5$；候选点 $19$ 覆盖坐标 $20$ 的烽火台，收益 $5$。三者并列，取坐标最小的 $1$，输出 5 1。

【样例 3 解释】

三个候选点距离最近的烽火台都超过了 $R = 1$，谁也建立不了通信，收益全为 $0$。按"并列时取坐标最小者"输出 0 -50。

【数据范围】

对于所有测试数据，保证：

• $1 \le n \le 2\times 10^5$，$1 \le m \le 2\times 10^5$；
• $0 \le R \le 2\times 10^9$；
• $-10^9 \le x_i \le 10^9$，$-10^9 \le y_j \le 10^9$；
• $x_1 < x_2 < \cdots < x_n$，$y_1 < y_2 < \cdots < y_m$；
• $1 \le b_i \le 10^9$。

测试点编号	$n \le$	$m \le$	特殊性质
$1$	$1$		无
$2$
$3$		$2$
$4$			C
$5$	$10$		无
$6$	$100$
$7$			A
$8$	$1000$		B
$9$			无
$10$	$2000$
$11$	$5000$
$12$			C
$13$			A
$14\sim15$	$20000$		无
$16$	$2\times 10^5$	$2\times 10^5$
$17$			B
$18$			无
$19$		$1$
$20$	$1$	$2\times 10^5$

• 特殊性质 A：所有 $b_i$ 相等。此时收益只取决于覆盖到的烽火台个数，会大量出现收益并列，必须正确处理"并列取坐标最小"。
• 特殊性质 B：$R = 2\times 10^9$，任何候选点都能覆盖全部烽火台。
• 特殊性质 C：$R = 0$。由于 $x_i$ 严格递增，只有坐标恰好与烽火台重合的候选点才有收益，其余候选点收益均为 $0$。