#220. 【NOI2016】网格

样例一

input

4
4 4 2
1 1
4 4
2 3 1
1 2
2 2 2
1 1
2 2
1 1 0



output

2
1
0
-1



限制与约定

$n,m$ 测试点编号 $c$
$nm \le 4$ 1 $c \le nm$
$nm \le 8$ 2
$nm \le 15$ 3
$nm \le 30$ 4
$nm \le 100$ 5
$nm \le 300$ 6
$nm \le 1000$ 7
$nm \le 20000$ 8 $c \le 5$
9 $c \le 15$
10 $c \le 30$
$n,m \le 20000$ $nm \le 20000$ 11 $\sum c \le 20000$
$nm \le 10^5$ 12
$nm \le 3 \times 10^5$ 13
$nm \le 10^6$ 14
$nm \le 10^9$ 15
$n,m \le 10^5$ 16 $\sum c \le 10^5$
$n,m \le 10^9$ 17 $c=0$
18 $c \le 1$
19 $c \le 2$
20 $c \le 3$
21 $c \le 10$
22 $c \le 30$
23 $c \le 300$
24 $\sum c \le 20000$
25 $\sum c \le 10^5$