题目描述

有 $n$ 座城市，每座城市都有且仅有一匹马。第 $i$ 座城市的马最多可以走 $v_i$ 的路程，它的速度为 $s_i$。第 $i$ 座城市到第 $j$ 座城市的 直接距离 为 $d_{i,j}$，若 $d_{i,j} = -1$ 则表示第 $i$ 座城市与第 $j$ 座城市 不直接 联通。
有 $q$ 次询问，每次询问给出两个点 $i,j$，表示询问从第 $i$ 座城市走到第 $j$ 座城市最少需要多长时间？
注：人在行驶中的任意时刻都必须骑马，人每到一个城市可以选择换上该城市的马继续前进。并且一匹马若可行走距离用尽，则必须更换为该城市的马，换马的过程假设不需要任何时间，骑着的马走到新的城市距离不会回复，保证每个数据至少存在一组解。

数据范围

对于 $100\%$ 的数据，$1 \le n, q \le 100, 1 \le v_i \le 10^{11}, 1 \le s_i \le 1000, -1 \le d_{i, j} \le 10 ^ {11}, d_{i, i} = -1, d_{i, j} \not= 0, i \not= j, 1 \le i, j \le n$。