#P16932. SGU317 Fast Ride
SGU317 Fast Ride
题目描述
皇家信使需要尽快从点 到达点 。点 在数轴上的坐标为 ,点 的坐标为正整数 。
在 到 的直线上有 个马厩。第 个马厩位于位置 ,其中有 匹马。
每匹马由两个参数描述:
- 速度 ;
- 最大奔跑距离 。
信使骑上一匹马后,最多可以让它奔跑 的距离,之后这匹马会精疲力尽。只要信使到达或经过某个马厩,就可以立即换乘该马厩中的任意一匹马,换马不消耗时间。
信使不允许步行。
求从 到达 的最短时间。
输入格式
第一行包含两个整数 :
- ;
- 。
接下来依次描述 个马厩。
每个马厩的第一行包含两个整数 :
- ;
- 。
随后 行,每行两个整数 ,描述一匹马:
- ;
- 。
所有马厩中的马匹总数不超过 。
允许多个马厩位于同一位置。
输出格式
输出信使到达 所需的最短时间,要求小数点后至少保留 位精度。
如果无法到达 ,输出 -1。
样例
10 3
5 2
1 100
10 3
0 1
1 50
8 1
2 3
6.30000000