В задаче 2157 Сумма для заданного дерева следует найти суммарную длину всех путей в дереве.

Сейчас мы предлагаем Вам решить обратную задачу. Задана матрица расстояний между всеми вершинами дерева с n вершинами. Необходимо определить, может ли эта матрица быть матрицей попарных расстояний между всеми вершинами взвешенного дерева. Все веса ребер дерева должны быть натуральными числами.

Входные данные

Первая строка содержит размер матрицы n (1 ≤ n ≤ 1000). Далее следует матрица расстояний: в n строках расположены n целых неотрицательных чисел, не превосходящих 109 - расстояния между парами вершин.

Выходные данные

Вывести YES, если такое дерево существует, и NO иначе.