e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Shortest paths - interesting graph problems

Sum on a tree reversed

The problem 2157 Sumмfor a given weighted tree asks to find the total length of all paths in the tree.

Now we propose you to solve the inverse problem. Given a distance matrix between all the nodes of a tree with n vertices. Determine whether this matrix is a matrix of pairwise distances between all vertices of weighted tree. All the weights of the tree edges should be positive integers.

Input

The first line contains the size of the matrix n (1n1000). Then given the matrix itself: n lines contain n nonnegative integers, not exceeding 109 - the distances between the pairs of vertices.

Output

Print YES, if such tree exists, and NO otherwise.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
0 5 1
5 0 6
1 6 0
Output example #1
YES