你玩过马里奥游戏吗？当然玩过，谁没玩过呢？！总之，马里奥游戏发布了新版本，这是一款卡丁车竞速游戏。你决定编写一个程序，找出完成每一关的最佳策略。

每一关的赛道可以建模为一条无限长的直线，直线上有一些特定位置的站点。每个站点都有一个整数，代表它在赛道上的位置。你的任务是以最少的移动次数，从第一个站点（位置最小的站点）到达最后一个站点（位置最大的站点）。

如果你有足够的加速金币，你可以直接在任意两个站点之间移动（你可以去往非相邻的站点，也可以根据需要返回位置更靠前的站点！）。在每一关中，你都有一些可以使用的加速金币。每个加速金币都有一个成本值和能量值。对于每次移动，你可以选择金币的任意子集，但每个金币在单次移动中只能使用一次。金币是永久性的，你可以在同一关的其他移动中再次使用这些金币。

要进行一次移动，你必须选择一个加速金币的子集，使得它们的成本总和不超过 $L$，且它们的能量值总和必须恰好等于你所移动的两个站点之间的位置绝对差。如果没有这样的子集，你就无法直接进行该次移动。

现在给定一些关卡的配置，你需要找出完成每一关所需的最少移动次数，或者指出无法完成该关卡。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量 ($1 \le T \le 100$)。接下来是各个测试用例，每个测试用例的第一行包含 3 个由空格分隔的整数 $N, M, L$ ($2 \le N \le 100, 1 \le M \le 100, 1 \le L \le 1,000$)，分别代表站点数量、加速金币数量以及每次移动中金币成本的最大总和。随后的一行包含 $N$ 个由空格分隔的唯一正整数（不一定有序，每个整数最大为 $1,000$），代表站点的位置。接下来的 $M$ 行，每行包含 2 个由空格分隔的整数 $C, V$ ($1 \le C, V \le 100$)，分别代表金币的成本和能量值。

输出格式

对于每个测试用例，打印一行，包含一个整数。如果无法从最左侧的站点到达最右侧的站点，则输出 -1；否则输出完成该任务所需的最少移动次数。

样例

输入 1

2
3 2 4
3 1 6
3 2
3 3
3 1 4
1 3 6
3 2

输出 1

2
-1

说明

在第一个测试用例中，站点位置为 $[3, 1, 6]$，你从 $1$ 出发，必须到达 $6$。你需要进行 2 次移动：使用金币 $(3, 2)$ 从 $1$ 移动到 $3$，再使用金币 $(3, 3)$ 从 $3$ 移动到 $6$。你不能直接从 $1$ 移动到 $6$（使用 $(3, 2)$ 和 $(3, 3)$），因为金币的成本总和超过了限制 $4$。