#P16932. SGU317 Fast Ride

SGU317 Fast Ride

题目描述

皇家信使需要尽快从点 AA 到达点 BB。点 AA 在数轴上的坐标为 00,点 BB 的坐标为正整数 BB。

在 AA 到 BB 的直线上有 NN 个马厩。第 ii 个马厩位于位置 XiX_i,其中有 MiM_i 匹马。

每匹马由两个参数描述:

  • 速度 vv;
  • 最大奔跑距离 dd。

信使骑上一匹马后,最多可以让它奔跑 dd 的距离,之后这匹马会精疲力尽。只要信使到达或经过某个马厩,就可以立即换乘该马厩中的任意一匹马,换马不消耗时间。

信使不允许步行。

求从 00 到达 BB 的最短时间。

输入格式

第一行包含两个整数 B,NB,N:

  • 1≤B≤1081\le B\le 10^8;
  • 1≤N≤50001\le N\le 5000。

接下来依次描述 NN 个马厩。

每个马厩的第一行包含两个整数 Xi,MiX_i,M_i:

  • 0≤Xi≤1080\le X_i\le 10^8;
  • Mi>0M_i>0。

随后 MiM_i 行,每行两个整数 vj,djv_j,d_j,描述一匹马:

  • 1≤vj≤1081\le v_j\le 10^8;
  • 1≤dj≤1081\le d_j\le 10^8。

所有马厩中的马匹总数不超过 10510^5。

允许多个马厩位于同一位置。

输出格式

输出信使到达 BB 所需的最短时间,要求小数点后至少保留 33 位精度。

如果无法到达 BB,输出 -1。

样例

10 3
5 2
1 100
10 3
0 1
1 50
8 1
2 3
6.30000000