e-olymp
Problems

Ancient manuscripts

Ancient manuscripts

In some ancient country there lived brothers. How many were them, we do not know exactly, but in historical sources mentioned that there were at least three. Time passed and they got children that scattered all over the world, and like their parents, each of them built own city. Again, over the time the number of relatives began to increase rapidly and they decided to build roads between some cities, and some relatives already even built the circular roads around their cities. The manuscript mentions that the number of cities in the country did not exceed 8000. Кроме того, в тех же рукописях содержались схематические карты, которые показывали наличие дорог между городами, или объездной дороги вокруг города. Карты имели вид квадратных матриц, в которых цифра 1 указывала на наличие дороги между городами, или вокруг города, или 0 в случае отсутствия таковой.

Explore the ancient manuscripts and answer the question: how many roads have been built between the cities?

Input

The first line contains the number of cities n, each of the next n lines contains n numbers that indicate the presence or absence of a corresponding road.

Output

Print the number of built roads between cities.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
5
1 1 1 1 0
1 0 1 0 1
1 1 1 0 1
1 0 0 0 1
0 1 1 1 1
Output example #1
7
Author Анатолий Присяжнюк