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