Sum on a tree reversed#7413

Sum on a tree reversed

1 second
128 megabytes
Easy

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 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 (1 \le n \le 1000). Then the matrix itself is given: lines contain nonnegative integers, not exceeding 10^9 - the distances between the pairs of vertices.

Output

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

Examples

Example 1

Loading
Loading