Problem E
Up and Away

Steve’s Retreat

Steve has set up $n$ bases on multiple mountains around his house, located at mountain $1$. He wants to fly from one base to another using his elytra and get to his vacation house at mountain $x$. Unfortunately, flying from one base to another takes time, and he can only do this from a taller mountain to a shorter mountain! If mountains are equal height, he can fly between them as well.

Fortunately, he has $k$ uses of fireworks, meaning he can also travel from a shorter mountain to a taller mountain! However, he doesn’t have much fireworks, so the total amount of elevation travelled upwards using fireworks throughout the whole trip must not exceed $k$. Please help Steve calculate the fastest time he can reach his vacation house, or determine that he can’t!

Input

The first line contains three space-separated integers $n$, $x$, and $k$, where $1 \leq n, k \leq 100$ and $1 \leq x \leq n$, the number of bases, the location of the vacation house and the amount of fireworks, respectively.

The second line contains $n$ space-separated integers $h_1, h_2, \ldots , h_ n$, where $h_ i$ ($1 \leq h_ i \leq 100$) is the height of the $i^{th}$ base’s mountain.

The next $n$ lines each contain $n$ integers each, where the $j^{th}$ integer on the $i^{th}$ of these $n$ lines is the time it takes to travel from the $i^{th}$ base to the $j^{th}$ base. The $i^{th}$ number on the $i^{th}$ of these $n$ lines will always be $0$. The time between mountains will not exceed $1\, 000$.

Output

If Steve can reach his vacation house, output a single integer, the minimum time Steve needs to reach his vacation house at base $x$. If he cannot reach his vacation house, output $-1$.

3 3 3
3 6 2
0 1 10
10 0 1
10 10 0

2