Escape the Haunted Castle (Part 2)

You are given a grid of passable cells and walls, along with a start, an exit, and some treasures. Each treasure can be picked up at most once. Find the minimum number of moves from the start to the exit; among all shortest paths, also find the maximum number of treasures that can be collected. If the exit cannot be reached, output -1 0.

输入格式

The first line contains rows cols; the second line contains the number of walls wallCount; each of the next wallCount lines contains a wall coordinate row col; then the number of treasures treasureCount is given; each of the next treasureCount lines contains a treasure coordinate row col; the last two lines give the start and exit coordinates respectively. All coordinates are 0-based. On-site constraints: 1 <= rows, cols <= 200; all coordinates lie inside the grid; the start and exit are not walls; treasure coordinates are distinct. Duplicate wall coordinates are treated as the same wall.

输出格式

Output two integers: the minimum number of steps and the maximum number of treasures that can be collected over all shortest paths. A treasure on the start cell counts toward the result; if the exit is unreachable, output -1 0.

样例 1

输入：

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

输出：

4 1

样例 2

输入：

2 2
0
0
0 0
1 1

输出：

2 0

样例 3

输入：

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

输出：

-1 0