27728번 - 개구리와 쿼리

$N \times N$ 크기의 $2$차원 배열로 이루어진 연못에 $Q$마리의 개구리들이 모여있다. 각 개구리들은 초기 위치 $\left(S_{x},S_{y}\right)$에서 배열의 오른쪽 끝$\left(X,N+1\right)$에 있는 육지에 도착해야 한다.

개구리들은 현재 칸에서 $Y$좌표가 $1$만큼 증가하는 방향 즉 오른쪽으로 이동할 수 있으며 이때 현재 칸에 적혀진 값만큼 시간이 소모된다. 또한 개구리마다 최대 한번 점프할 수 있으며 점프를 한다면 개구리마다 정해진 하한 값 $L$ 이상 점프해야 한다.

점프는 $X$좌표가 감소하는 방향으로 이동 즉 위쪽으로 이동하는 것이며 시간이 소모되지 않는다.

개구리의 초기 위치와 점프 하한 값이 다음과 같은 쿼리 형태로 주어질 때

• $S_{x}$ $S_{y}$ $L$ : 개구리의 초기 위치가 $\left(S_{x},S_{y}\right)$ 이고 최대 한번 $L$ 이상의 양의 정수 값 $T$만큼 점프할 수 있을 때 육지에 도달하는 데 걸리는 최단 시간을 출력하라. $\left(S_{x} > L\right)$

각 쿼리에 대해서 옳은 답을 차례대로 출력하자.

입력의 첫 줄에 $2$차원 배열의 크기를 나타내는 $N$과 개구리의 수 $Q$가 공백으로 구분되어 정수로 주어진다.$(3 \le N \le 500;$ $1 \le Q \le 200 \, 000)$

입력의 두 번째 줄부터 $N$개의 줄에 배열 $A$에 적힌 값이 공백으로 구분되어 정수로 주어진다.$i+1$번째 줄의 $j$번째 수는 배열의 $i$번째 행 $j$번째 열의 적힌 값 $A[i][j]$을 나타낸다.$\left(0 \le A[i][j] \le 10\,000\right)$

입력의 $N+2$ 줄부터 $Q$개의 줄에 쿼리가 정수로 주어진다.$(0 \le L < S_{x} \le N;$ $1 \le S_{y} \le N)$

$Q$개의 줄에 차례대로 쿼리의 정답을 정수로 출력하라.