Escape the Haunted Castle (Part 2)

A grid contains walls, a start, an exit, and treasures. You can only move up, down, left, or right. Find the minimum number of steps to reach the exit; if there are several shortest paths, return the maximum number of treasures that can be collected on one of them. If the exit is unreachable, return -1 0. A treasure is picked up once when you reach it.

输入格式

The input gives rows cols, the wall coordinates, the treasure coordinates, start, and end; this site specifies that coordinates are 0-based, each coordinate is on its own line, the grid side lengths are 1..200, all coordinates are valid, start/end are not walls, and treasure coordinates are distinct.

输出格式

Output the minimum number of steps and the maximum number of treasures that can be picked up on a shortest path. A treasure on the start cell also counts.

样例 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