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

Output

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

Examples