Description↵
========↵
↵
There is a Hydra, that you need to slay: it has **n** types of heads, numbered from 1 to 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↵
========↵
↵
Minimum amount of strikes to slay the Hydra. Write -1 if it is impossible↵
↵
ПримерыExamples↵
-------↵
↵
###ПримерExample 1↵
####ВходInput:↵
↵
- 3↵
- 1 0 0↵
- 0 1 2↵
- 0 0 0↵
- 0 0 0↵
↵
Выход#### Output:↵
↵
- 4↵
↵
###ПримерExample 2↵
####ВходInput:↵
↵
- 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↵
↵
####ВыходOutput:↵
↵
- 31↵
↵
###ПримерExample 3:↵
####ВходInput:↵
↵
- 1↵
- 1↵
- 1↵
↵
####ВыходOutput:↵
↵
- -1↵
========↵
↵
There is a Hydra, that you need to slay: it has **n** types of heads, numbered from 1 to 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↵
========↵
↵
Minimum amount of strikes to slay the Hydra. Write -1 if it is impossible↵
↵
-------↵
↵
###
####
↵
- 3↵
- 1 0 0↵
- 0 1 2↵
- 0 0 0↵
- 0 0 0↵
↵
↵
- 4↵
↵
###
####
↵
- 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↵
↵
###
####
↵
- 1↵
- 1↵
- 1↵
↵
####
↵
- -1↵
