Деревянная матрица
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мебибайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим квадратную матрицу размера $$$n \times n$$$, состоящую из неотрицательных целых чисел. Матрица симметрична относительно главной диагонали, которая, в свою очередь, содержит лишь нули. Такая матрица называется деревянной, если существует такое неориентированное дерево $$$T$$$ на $$$n$$$ вершинах с рёбрами положительных длин, что в каждой ячейке матрицы $$$(i, j)$$$ записано расстояние между вершинами $$$i$$$ и $$$j$$$ в этом дереве.

Дана матрица. Проверьте, является ли она деревянной.

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

В первой строке дано целое число $$$n$$$ — размер матрицы ($$$1 \le n \le 1000$$$). В каждой из следующих $$$n$$$ строк задано по $$$n$$$ целых чисел $$$d_{i,j}$$$ — элементы матрицы ($$$0 \le d_{i,j} \le 10^9$$$). Матрица симметрична относительно главной диагонали. На главной диагонали стоят нули, а вне её — строго положительные целые числа.

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

Выведите «Yes» или «No» в зависимости от того, является ли матрица деревянной. Регистр букв не важен.

Примеры

Входные данные
3
0 1 3
1 0 2
3 2 0
Выходные данные
Yes 
Входные данные
3
0 1 3
1 0 1
3 1 0
Выходные данные
No