Labyrinth Adventure Scoring

You are given an underground labyrinth that is represented by an N×N grid. Some cells are empty, some contain an automatic score counter (denoted by *) and some are obstacles (denoted by #). There are P players. Each player starts at a given cell in the grid. It is guaranteed that no starting cell contains an obstacle. Every minute, each player sends scouts in the four cardinal directions (up, down, left, right) to all adjacent cells that are not obstacles. Each player has an unlimited number of scouts so that from their starting cell the movement can be seen as a simultaneous multi‐source expansion.

When a scout reaches a cell that has an automatic score counter, the player owning that scout will gain 1 point if and only if the cell is reached at the minimum number of moves among all players. If two or more players’ scouts arrive at the same counter at the same minute (i.e. achieving the same minimum distance), then each of those players earns 1 point simultaneously. After a counter is claimed, it will not contribute any further score. Note that if a cell is unreachable by all players, it gives no score.

Your task is to determine two values:

• The maximum score attained by any single player.
• The total score summed over all players.
</p>

The distances are computed in terms of the number of moves (each move goes from a cell to an adjacent one in one minute) and any cell with an obstacle (#) is not accessible.

In mathematical notation, if we denote by \(d_p(i,j)\) the minimum number of moves that player \(p\) needs to reach cell \((i,j)\), then for each cell \((i,j)\) with a counter (*), let \(d_{min}(i,j)=\min_{p} d_p(i,j)\). Every player \(p\) such that \(d_p(i,j)=d_{min}(i,j)\) (and \(d_p(i,j)\) is finite) earns 1 point.

inputFormat

The first line contains two integers N and P where N (\(1 \leq N \leq 1000\)) is the size of the grid and P is the number of players.

The next P lines each contain two integers r and c (0-indexed) representing the starting row and column for each player.

The following N lines each contain a string of length N consisting of the characters:

• * : a cell with an automatic score counter
• . : an empty cell
• # : an obstacle (cell not accessible)

outputFormat

Output two integers separated by a space: the maximum score among all players and the total score summed over all players.

sample

3 2
0 0
2 2
*.*
.*.
*.*

4 8

</p>