Difference between ru5 and en1,
changed 1020 character(s)
ОписаниеDescription↵
========↵
↵
Перед вами мифическая гидра: у неё **n** типов голов, пронумерованных отThere is a Hydra, that you need to slay: it has **n** types of heads, numbered from 1 доto n (от «нижних» к «верхним»). При ударе по голове одного типа эта голова отрубается, но у гидры тут же возникают дополнительные головы, причём каждая голова создаёт копию голов других типов. Ваша задача — добить гидру, то есть добиться нулевого количества голов всех типов, затратя минимальное число ударов. Нулевым количеством считается тот момент, когда после сруба последней головы, другие головы не будут появляться.↵
↵
Вход↵
========↵
На вход подаётся набор данных. Первая строка содержит число n — количество типов голов гидры (1 ≤ n ≤ 2000). Далее идёт строка, содержащая массив a из n элементов a_1 ... a_n (0 ≤ a_i ≤ 10^9) — начальные количества голов. Затем подаётся n строк по n целых чисел, задающих матрицу«lower» till «higher»). You can strike one head and cut it, but every head produces other heads. Your goal is to slay the hydra with minimum amount of strikes. Hydra is killed, when after cutting the last head, other won't appear.↵
↵
Input↵
========↵
First string contains n — nuuber of head types (1 ≤ n ≤ 2000). The second string contains n elements: a_1 ... a_n (0 ≤ a_i ≤ 10^9) — starting quantity of every heads. Then comes n string, containing n nums (matrix b).↵
↵
ВыходOutput↵
========↵
↵
Одно целое число — минимальное общее количество ударов, необходимое для уничтожения всех голов гидры. Если гидру невозможно убить, выведите -1Minimum amount of strikes to slay the Hydra. Write -1 if it is impossible↵
↵
Примеры↵
-------↵
↵
### Пример 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↵
