D. Уроки дизайна задач: обратные задачи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Помимо прочего, можно придумывать новые задачи, решая обратные задачи к старым задачам. Обратная задача — это когда в качестве входных данных даются выходные данные исходной задачи и нужно сгенерировать в качестве выходных данных такие входное данные, что решение исходной задачи на них выдавало бы заданные входные данные. Самая сложная задача Topcoder Open 2014 раунда 2C, InverseRMQ, является хорошим примером такого подхода.

Попробуем придумать новую задачу таким способом. В качестве основы используем следующую задачу: задано дерево; подсчитайте расстояние между всеми парами его вершин. Да, это просто. Но обратная версия этой задачи куда сложнее: задана матрица расстояний размера n × n. Определите, может ли данная матрица быть матрицей всех попарных расстояний между вершинами взвешенного дерева (все веса должны быть целыми положительными числами).

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

В первой строке записано целое число n (1 ≤ n ≤ 2000) — размер матрицы (и количество вершин соответствующего дерева).

В следующих n строках содержится по n целых чисел di, j (0 ≤ di, j ≤ 109) — расстояние между вершиной i и вершиной j дерева.

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

Если такое дерево существует, выведите «YES», в противном случае выведите «NO».

Примеры
Входные данные
3
0 2 7
2 0 9
7 9 0
Выходные данные
YES
Входные данные
3
1 2 7
2 0 9
7 9 0
Выходные данные
NO
Входные данные
3
0 2 2
7 0 9
7 9 0
Выходные данные
NO
Входные данные
3
0 1 1
1 0 1
1 1 0
Выходные данные
NO
Входные данные
2
0 0
0 0
Выходные данные
NO
Примечание

В первом примере необходимое дерево существует. Оно состоит из ребра между вершинами 1 и 2 с весом 2 и ребра между вершинами 1 и 3 с весом 7.

Во втором примере дерево не существует, потому что d1, 1 должно равняться 0, а оно равняется 1.

В третьем примере дерево не существует, потому что d1, 2 должно равняться d2, 1.