2017年中国大学生程序设计竞赛秦皇岛站即将到来！共有 $n$ 支队伍参赛，比赛在一个巨大的圆桌上进行，圆桌上有 $m$ 个座位，按顺时针方向编号为 $1$ 到 $m$。第 $i$ 支队伍坐在第 $s_i$ 号座位上。

BaoBao 是一位程序设计竞赛爱好者，他在赛前对比赛结果做了 $p$ 次预测。每条预测的形式为 $(a_i, b_i)$，表示第 $a_i$ 支队伍在第 $b_i$ 个时间单位解出了一道题。

众所周知，当一支队伍解出一道题时，会获得一个气球作为奖励。如果气球送达得太晚，参赛者会感到不高兴。如果一支队伍在第 $t_a$ 个时间单位解出一道题，而气球在第 $t_b$ 个时间单位送达，那么该队伍的不高兴程度将增加 $(t_b - t_a)$。为了及时发放气球，比赛组织者购买了一个气球机器人。

在比赛开始时（即第 $1$ 个时间单位开始时），机器人会被放置在第 $k$ 号座位上，并开始绕桌移动。如果机器人经过一支在上次访问后赢得了气球的队伍，它会将该队伍应得的所有气球发放给他们。在每个时间单位内，以下事件将按顺序发生：

1. 机器人移动到下一个座位。也就是说，如果机器人当前在第 $i$ ($1 \le i < m$) 号座位，它将移动到第 $(i + 1)$ 号座位；如果机器人当前在第 $m$ 号座位，它将移动到第 $1$ 号座位。
2. 参赛者根据 BaoBao 的预测解出一些题目。
3. 如果需要，机器人向当前位置的队伍发放气球。

BaoBao 希望最小化所有队伍的总不高兴程度。你的任务是选择机器人的起始位置 $k$，并根据 BaoBao 的预测计算所有队伍的最小总不高兴程度。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $n, m$ 和 $p$ ($1 \le n \le 10^5, n \le m \le 10^9, 1 \le p \le 10^5$)，分别表示参赛队伍数量、座位数量和预测数量。

第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$ ($1 \le s_i \le m$，且对于所有 $i \neq j$，$s_i \neq s_j$)，表示每支队伍的座位号。

接下来的 $p$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \le n, 1 \le b_i \le 10^9$)，表示第 $a_i$ 支队伍根据 BaoBao 的预测在第 $b_i$ 个时间单位解出一道题。

保证所有测试数据中 $n$ 的总和与 $p$ 的总和均不超过 $5 \times 10^5$。

输出格式

对于每组测试数据，输出一个整数，表示根据 BaoBao 的预测，所有队伍的最小总不高兴程度。

样例

样例输入 1

4
2 3 3
1 2
1 1
2 1
1 4
2 3 5
1 2
1 1
2 1
1 2
1 3
1 4
3 7 5
3 5 7
1 5
2 1
3 3
1 5
2 5
2 100 2
1 51
1 500
2 1000

样例输出 1

1
4
5
50

说明

对于第一个样例测试数据，如果我们选择起始位置为第 $1$ 号座位，总不高兴程度为 $(3 - 1) + (1 - 1) + (6 - 4) = 4$。如果我们选择第 $2$ 号座位，总不高兴程度为 $(2 - 1) + (3 - 1) + (5 - 4) = 4$。如果我们选择第 $3$ 号座位，总不高兴程度为 $(1 - 1) + (2 - 1) + (4 - 4) = 1$。因此答案为 $1$。

对于第二个样例测试数据，如果我们选择起始位置为第 $1$ 号座位，总不高兴程度为 $(3 - 1) + (1 - 1) + (3 - 2) + (3 - 3) + (6 - 4) = 5$。如果我们选择第 $2$ 号座位，总不高兴程度为 $(2 - 1) + (3 - 1) + (2 - 2) + (5 - 3) + (5 - 4) = 6$。如果我们选择第 $3$ 号座位，总不高兴程度为 $(1 - 1) + (2 - 1) + (4 - 2) + (4 - 3) + (4 - 4) = 4$。因此答案为 $4$。