Bob is playing a game on a 2D grid with $n$ rows and $m$ columns. He starts at the top-left corner, cell $(1, 1)$, and his goal is to reach the bottom-right corner, cell $(n, m)$.↵
↵
Bob can move in the following ways:↵
↵
- Choose an index $i$ ($1 \le i \le k$) and:↵
- Move **down** by $A[i]$ rows: from $(x, y)$ to $(x + A[i], y)$ ↵
- Move **right** by $B[i]$ columns: from $(x, y)$ to $(x, y + B[i])$ ↵
- Move **diagonally** down-right by $C[i]$ cells: from $(x, y)$ to $(x + C[i], y + C[i])$↵
↵
Each such move has a cost of $1$.↵
↵
You are also guaranteed that each of the arrays $A$,$B$ and $C$ contain $1$.↵
↵
You are given the integers $n$, $m$, $k$ and the arrays $A$, $B$, and $C$, each of length $k$. Your task is to compute the **minimum cost** to reach cell $(n, m)$ starting from $(1, 1)$. ↵
↵
$n,m,k\leq 10^3$↵
↵
Bob can move in the following ways:↵
↵
- Choose an index $i$ ($1 \le i \le k$) and:↵
- Move **down** by $A[i]$ rows: from $(x, y)$ to $(x + A[i], y)$ ↵
- Move **right** by $B[i]$ columns: from $(x, y)$ to $(x, y + B[i])$ ↵
- Move **diagonally** down-right by $C[i]$ cells: from $(x, y)$ to $(x + C[i], y + C[i])$↵
↵
Each such move has a cost of $1$.↵
↵
You are also guaranteed that each of the arrays $A$,$B$ and $C$ contain $1$.↵
↵
You are given the integers $n$, $m$, $k$ and the arrays $A$, $B$, and $C$, each of length $k$. Your task is to compute the **minimum cost** to reach cell $(n, m)$ starting from $(1, 1)$. ↵
↵
$n,m,k\leq 10^3$↵
