Buying Potions

Jun-gyeom is an adventurer. Before setting out on an adventure, he has to prepare thoroughly.

Before leaving, Jun-gyeom wants to buy all $N$ kinds of potions. At the potion shop, he finds that each potion is numbered from 1 to $N$. The shop is running a special event today: buying a certain potion gives discounts on some other potions.

The original price of the $i$-th potion is $c_i$ coins. When you buy the $i$-th potion, the prices of $p_i$ other potions go down.

Discounts stack. For example, suppose buying potion 1 takes 1 coin off potion 3, and buying potion 2 takes 2 coins off potion 3. If you buy both, then buying potion 3 afterward gives a discount of 3 coins. A price never drops below 0. For example, if a potion originally costs 5 coins and is discounted by more than 4 coins, its price becomes 1 coin.

Jun-gyeom was excited to start buying, but then he realized that the order of purchases matters. Find the minimum total cost of buying all the potions.

The first line contains $N$, the number of potion kinds.

The second line contains the prices $c_i$ separated by spaces ($1 \le i \le N$).

The next lines give the discount information for each potion, for $i$ from 1 to $N$ ($1 \le i \le N$).

Each block starts with $p_i$. The next $p_i$ lines each contain a potion number $a_j$ and a discount amount $d_j$. This means that after you buy potion $i$, potion $a_j$ is discounted by $d_j$ coins.

Print the minimum number of coins needed to buy all the potions, on the first line.

• $2 \le N \le 10$
• $1 \le c_i \le 1\,000$
• $0 \le p_i \le N-1$
• For each $i$, all $a_j$ are distinct and $a_j \neq i$
• $1 \le d_j \le 1\,000$