Under construction

Still being built. Things may change

Chain Disappearance Puzzle

Time limit1sMemory limit256 MB

Summary
Repeatedly remove horizontal runs of three or more equal digits from a 5-column board, drop stones above into gaps, and sum the removed digits.
Level

Easy3 of 10

Topics
Simulation, Matrix, Implementation
Solved
No attempts yet

Problem

You are playing a puzzle. The puzzle uses an upright board of HH rows by 5 columns of cells, as in the figure below. Each cell holds one stone engraved with a digit from 1 to 9. When three or more stones in horizontally adjacent cells carry the same digit, those stones disappear. If stones sit above a cell whose stone disappeared, they drop down and fill the vacancy.

The puzzle proceeds in the following steps.

  1. When three or more stones in horizontally adjacent cells carry the same digit, those stones disappear. Every group that meets the condition disappears at the same time.
  2. When stones sit above the emptied cells, they drop down so that the emptied cells are filled.
  3. After all drops finish, if one or more groups still meet the disappearance condition, return to step 1 and repeat.

The score of the puzzle is the sum of the digits on the stones that disappeared.

Write a program that computes the score of a given placement of stones.

Input

The input consists of several datasets. Each dataset has the following form.

Board height HH

Stone placement of row 1

Stone placement of row 2

...

Stone placement of row HH

The first line gives the height HH (1≤H≤101 \le H \le 10) of the puzzle board. The next HH lines give the stone placement of each row, from the top row down. A placement is five digits from 1 to 9 separated by a space, engraved on the five stones of that row in the same order.

The input ends with a line containing a single zero.

Output

For each dataset, output the score on one line. An output line contains no characters other than the digits of the score.

Examples3

  1. Example 1

    Input
    1
6 9 9 9 9
5
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
10
3 5 6 5 6
2 2 2 8 3
6 2 5 9 2
7 7 7 6 1
4 6 6 4 9
8 9 1 1 8
5 6 1 8 1
6 8 2 1 2
9 6 3 3 5
5 3 8 8 8
5
1 2 3 4 5
6 7 8 9 1
2 3 4 5 6
7 8 9 1 2
3 4 5 6 7
3
2 2 8 7 4
6 5 7 7 7
8 8 9 9 9
0
    Expected output
    36
38
99
0
72

  2. Example 2

    Input
    1
1 2 3 4 5
0
    Expected output
    0

  3. Example 3

    Input
    1
7 7 7 7 7
0
    Expected output
    35