题目描述

小冷手想要建造一个围栏来圈住他的奶牛们的草地。然而，为了让围栏有效，它必须包含所有的 $m$ 个草地位置。否则，奶牛们可能会反抗他。

为了解决这个问题，小冷手向星际奶牛公司寻求了帮助。然而，公司只给他提供了 $n$ 个围栏点，他只能从一个点向另一个点建造围栏。最终的成本将取决于所使用的点数。

小冷手知道最划算的围栏应该是凸包，但他不知道建造它确切需要多少个点。因此，他来找你帮忙解决这个问题：

确定建造一个能完全围住所有 $m$ 个草地位置所需的最小点数。

附注：如果围栏与任何草地位置相交，我们不认为该位置被完全围住。

输入格式

输入的第一行包含整数 $T$（$1 \leq T \leq 10$），表示测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 500, 1 \leq m \leq 500$）——围栏点的数量和草地位置的数量。

接下来的 $n$ 行，每行包含围栏点的描述。每行包含两个整数 $x_i$ 和 $y_i$（$-10^9 \leq x_i, y_i \leq 10^9$），描述位于 $(x_i, y_i)$ 的围栏点 $a_i$。

接下来的 $m$ 行，每行包含草地位置的描述。每行包含两个整数 $x_i$ 和 $y_i$（$-10^9 \leq x_i, y_i \leq 10^9$），描述位于 $(x_i, y_i)$ 的草地位置 $b_i$。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $4000$。

输出格式

对于每个测试用例，如果存在任何解决方案，则在一行中输出一个整数，表示围栏的最小成本。否则，输出 $-1$。

2
4 1
1 1
1 -1
-1 -1
-1 1
0 0
4 1
1 1
1 -1
-1 -1
-1 1
1 0

4
-1