Problem B
Up and Away
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$.
Sample Input 1 | Sample Output 1 |
---|---|
3 3 3 3 6 2 0 1 10 10 0 1 10 10 0 |
2 |