原试题 pdf 见#5034.「P154」马附件或直链。
你是能看到第四题的 friends 呢。 ——rivenhe
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
N 个城市，第 i 座城市的坦克最多以 S_i 的速度行驶 E_i 的距离。
第 a 座城市到第 b 座城市直接道路的长度为 D_{ab} ， −1 代表路不存在。
M 次询问，第 k 次询问询问从 U_k 出发到 V_k 最少需要多少的时间。
要求整个过程中必须开坦克行进，坦克不能加油，所以在一座城市的时候只能换成该城市的坦克继续前进或者不换。每次询问一定存在至少一组解。
第一行两个整数 N, M 。
接下来 N 行每行两个整数表示 E_i, S_i 。
接下来 N 行每行 N 个整数表示 D_{ij} 。
接下来 M 行每行两个整数表示 U_k, V_k 。
输出共 M 行每行 M 个数表示答案，保留六位小数。
3 1 2 3 2 4 4 4 -1 1 -1 -1 -1 1 -1 -1 -1 1 3
0.583333
4 1 13 10 1 1000 10 8 5 5 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 10 -1 -1 -1 -1 1 4
1.200000
对于 5\% 的数据， N \leq 3 。
对于 55\% 的数据， N \leq 10 。
对于 70\% 的数据， N \leq 20 。
对于 80\% 的数据， N \leq 30 。
对于 100\% 的数据， 1 \leq N, M \leq 100, 1 \leq E_i \leq 10^9, 1 \leq S_i \leq 1000, −1 \leq D_{ab} \leq 10^9, D_{aa} = −1, D_{ab} \neq 0, U_k \neq V_k 。