题目描述

你是 CSGO 战队的新生，为了提升自己的装备搭配水平，你找到传说中的 "GO学长" 请教武器搭配的技巧。

GO学长告诉你，选武器不仅要看单件武器强不强，还要看主武器和副武器的配合。比如，AWP 超远射程配上 CZ75 快速近战能形成互补，AK47 强力爆头搭配 Desert Eagle 灵活爆发同样所向披靡。

学长最后给你留下了一个考验：根据一大堆武器的数据，选出一组最佳组合，让你的综合评估值最大化。能做到的话，你就能正式成为战队主力！

在 CSGO 中有 $n$ 个主武器（Main Weapons）和 $m$ 个副武器（Secondary Weapons）。你只能各选一把主武器和副武器。每把武器都有一个综合评分 $S$（评分越高越好），以及 $K$ 个性能指标 $x[1], x[2], \dots, x[K]$（如射程、射速、后坐力、重量……）。

为了追求武器之间的性能互补，你希望主武器和副武器在各性能指标上差异越大越好。例如，AWP + CZ75、AK47 + Desert Eagle 都是不错的组合。

对于任意一把主武器 MW 和一把副武器 SW，其总评估值计算公式为：

$\mathrm{Eval}(MW,SW) = S_{MW} + S_{SW} + \sum_{i=1}^K \bigl\lvert x^{(MW)}_i - x^{(SW)}_i \bigr\rvert.$

现在，给定所有主武器和副武器的信息，请你选出一对武器，使得上述评估值最大，并输出该最大值。

输入格式

第一行包含一个正整数 $T(1\le T\le 100 )$，表示数据组数。
对于每组数据：
第一行行包含三个正整数 $n(1 \le n \le 10^5), m(1 \le m \le 10^5), K(1 \le K \le 5)$。
接下来 $n$ 行，每行 $K+1$ 个整数，分别是主武器的 $S, x[1], x[2], \dots, x[K] (0 \le S \le 10^9, |X[i]| \le 10^9)$。

再接着 $m$ 行，每行 $K+1$ 个整数，分别是副武器的 $S, x[1], x[2], \dots, x[K] (0 \le S \le 10^9, |X[i]| \le 10^9)$。

题目保证：所有测试数据中所有$n+m$的和$\le3 \times 10^5$

输出格式

共 $T$ 行，第 $i$ 行输出第 $i$ 组数据的最大评估值。

样例

2
2 2 1
0 233
0 666
0 123
0 456
2 2 1
100 0 1000 100 1000 100
100 0

543
2000

提示

对于第一组测试数据，选第$2$把主武器和第$1$把副武器评估值最大，为$|(0 + 666) - (0 + 123)| = 543$。