Описание

Перед вами мифическая гидра: у неё n типов голов, пронумерованных от 1 до n (от «нижних» к «верхним»). При ударе по голове одного типа эта голова отрубается, но у гидры тут же возникают дополнительные головы, причём каждая голова создаёт копию голов других типов. Ваша задача — добить гидру, то есть добиться нулевого количества голов всех типов, затратя минимальное число ударов. Нулевым количеством считается тот момент, когда после сруба последней головы, другие головы не будут появляться.

Вход

На вход подаётся набор данных. Первая строка содержит число n — количество типов голов гидры (1 ≤ n ≤ 2000). Далее идёт строка, содержащая массив a из n элементов a_1 ... a_n (0 ≤ a_i ≤ 10^9) — начальные количества голов. Затем подаётся n строк по n целых чисел, задающих матрицу b.

Выход

Одно целое число — минимальное общее количество ударов, необходимое для уничтожения всех голов гидры. Если гидру невозможно убить, выведите -1

Примеры

Пример 1

Вход:

• 3
• 1 0 0
• 0 1 2
• 0 0 0
• 0 0 0

Выход:

• 4

Пример 2

Вход:

• 5
• 1 1 1 1 1
• 0 1 0 0 0
• 0 0 1 0 0
• 0 0 0 1 0
• 0 0 0 0 1
• 0 0 0 0 0

Выход:

• 31

Пример 3:

Вход:

• 1
• 1

• 1

  Выход:

• -1