过桥问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

GDOI工作组遇到了一个运输货物的问题。现在有N辆车要按顺序通过一个单向的小桥。由于小桥太窄,不能有两辆车并排通过,所以在桥上不能超车。另外,由于小桥建造的时间已经很久,所以只能承受有限的重量,记为Max(吨),即任意时刻在桥上行驶的车辆的总重量不能超过Max(吨)。所以,车辆在过桥的时候必须要有管理员控制,将这N辆车按初始的顺序分组,每次让一个组过桥,并且只有在一个组中所有的车辆全部过桥以后才让下一辆车辆上桥。现在,每辆车的重量和最大速度是已知的,而每组车的过桥时间由该组中速度最慢的那辆车决定。现在请你编一个程序,将这N辆车分组,使得全部车辆通过小桥的时间最短。

Input

输入的第1行有3个数,分别为Max(吨),Len(桥的长度,单位:km),N(3个数之间用一个或多个空格分开)。接下来有N行,每行两个数,第i行的两个数分别表示第i辆车的重量(吨)和最大速度(km/h)。

注意:所有输入都为整数,并且任何一辆车的重量都不会超过Max。

Output

输出数据只有一行,输出全部车辆通过小桥的最短时间(minute),精确到小数点后一位。

Sample Input

100 5 10
40 25
50 20
50 20
70 10
12 50
9 70
49 30
38 25
27 50
19 70

Sample Output

75.0

Hint

Source