Marisa has $n$ gardens. Each garden needs to be watered daily. For each garden, Marisa has two options:
- Dig a well in this garden.
- Build a pipeline from a garden that already has water to this garden.
Find the minimum cost to water all $n$ gardens.
### Input
- The first line contains an integer $n$.
- The second line contains $n$ integers $a_i$, representing the cost of digging a well for each garden $i$.
- The next $n$ lines each contain $n$ integers $b_{ij}$, representing the cost of connecting garden $i$ and garden $j$.
### Output
- Print a single integer, the minimum cost.
### Constraints
- $1 \leq n \leq 500$.
- $1 \leq a_i, b_{ij} \leq 1000$.
- $b_{ij} = b_{ji}$.
### Example
Input:
```
4
5 4 4 3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
```
Output:
```
9
```
Explanation: Dig a well in garden $4$. Build pipelines between garden $1$ and all other gardens.
