시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 1024 MB0000.000%

문제

The largest picture stolen by the gangsters from the State Gallery is to be evaluated by an expert before it is sold on the black market. The composition of the picture clearly follows mainstream tendencies in contemporary AI art. The picture can be viewed as a grid of square cells where each cell is either empty or non-empty. A non-empty cell contains exactly one of these objects: a sun, a house, a chupacabra, a left slope, a right slope, a bird, a drake, or a grill. Two cells are adjacent if they share an edge in the grid. A connection between two cells is a sequence of cells which contains both given cells and in which each two consecutive cells are adjacent in the picture. An area is a set of cells. It is connected if there is a connection between any two cells in the area.

The value of the picture is the total of all values generated by all rules listed below.

Suns: A non-empty cell, not containing a sun, is illuminated by a sun if there is no other object on a straight line between the cell and another cell with a sun. The straight line may be horizontal, vertical or diagonal (both diagonal directions apply). When a cell is illuminated by multiple suns it is still counted only once. A sun cannot illuminate itself. Each illuminated cell generates 100$.

Biggest bird: A drake is a bird. A flock of birds is maximal connected area of cells each of which contains a bird. The width of a flock is the length of a maximum contiguous sequence of cells on one line in a flock. A flock of birds generates 500$ · (width of the flock).

Flock perimeter: Each flock of birds (see previous rule) generates value 60$ · (flock perimeter). Flock perimeter is the total number of edges each of which separates a flock cell from a cell which does not contain a bird or from the outside of the picture.

House view up: When an empty cell is located above a cell containing a house, it is in the same column, and there is no non-empty field between the empty cell and the house, the empty cell generates 10$.

3 × 3 blocks: Each unique 3 × 3 block (possibly overlapping) generates 1$.

Animals I: Each edge between a cell with an animal and an empty cell generates 15$.

Freedom: Cell X is a freedom cell if it is either adjacent to the picture border or there is a connection between a cell adjacent to the picture border and a cell adjacent to X and the connection contains only empty cells. Each non-empty freedom cell generates 7$.

Chupacabra: A drake is a bird. Each bird which can be reached by a chupacabra performing one chess knight move in the grid generates 200$.

Peaks: A pair of adjacent cells with characters “/\” (left slope and right slope, in this order) on one line is a peak. Peak summit is an imaginary point in the middle of the segment connecting the uppermost points of both symbols in the peak. Peak value is equal to the maximum Manhattan distance from the peak summit to the summit of another peak in the grid. Note that peak value is an integer. Each peak P generates 50$ · (P value) when there are at least two peaks in the picture. Otherwise, a single peak in the picture generates 0$.

Drake/grill: Each cell with a drake and with at least one adjacent cell with a grill generates 500$.

Minimum frequency: Frequency of an object X is the number of the objects (including X) of the same type as X in the entire picture. Each single object which frequency is minimum among all objects in the picture generates 10$.

Empty fields: Each empty field generates 1$.

Animals II: All animals in the picture together generate single value 1$ · (number of chupacebras) · (number of birds which are not drakes) · (number of drakes).

House view down: When an empty field is located above a house, is in the same column, and there is no non-empty field between the empty field and the house, the empty field generates 5$.

Grill/drake: Each cell with a grill and with at least one adjacent cell with a drake generates 50$.

Houses and grills: Houses and grills in the picture generate 3$ · min { number of all houses, number of all grills }.

입력

The first input line contains one integer N (1 ≤ N ≤ 50), the number of the rows and the columns in the picture. Next, there are N lines, each specifies one line in the picture. One character on the line represents one cell and its contents.

The interpretation of particular characters in the picture representation follows: empty cell “ ” (space), sun “*”, house “^”, chupacabra “!”, left slope “/”, right slope “\”, bird “v”, drake “D”, grill “G”.

출력

Print one integer, the value of the input picture.

예제 입력 1

9
 *^!/\vDG
 *^!/\vDG
 *^!/\vDG
 *^!/\vDG
 *^!/\vDG
 *^!/\vDG
 *^!/\vDG
 *^!/\vDG
 *^!/\vDG

예제 출력 1

12672

예제 입력 2

3
!  
  v
 D 

예제 출력 2

2059