eolymp
bolt
Try our new interface for solving problems
Problems

Ancient manuscripts

Ancient manuscripts

Time limit 1 second
Memory limit 128 MiB

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 data

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 data

Print the number of built roads between cities.

Examples

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 Анатолий Присяжнюк