題目描述

GDOI工作組遇到了一個運輸貨物的問題。現在有N輛車要按順序通過個單向的小橋，由於小橋太窄，不能有兩輛車並排通過，所以在橋上不能超車。另外，由於小橋建造的時間已經很久，所以只能承受有限的重量，記為Max(噸)，即任意時刻在橋上行駛的車輛的總重量不能超過Max(噸)。所以，車輛在過橋的時候必須要有管理員控制，將這N輛車按初始的順序分組，每次讓一個組過橋，並且只有在一個組中所有的車輛全部過橋以後才讓下組車輛上橋。現在，每輛車的重量和最大速度是已知的，而每組車的過橋時間由該組中速度最慢的那輛車決定。現在請你編一個程式，將這N輛車分組，使得全部車輛通過小橋的時間最短。

輸入格式

第1行有3個數，分別為Max(噸)，Len(橋的長度，單位：km)，N(3個數之間用一個或多個空格分開)。接下來有N行，每行兩個數，第i行的兩個數分別表示第i輛車的重量(噸)和最大速度(km/h)。

注意：所有的輸入都為整數，並且任何一輛車的重量都不會超過Max.

輸出格式

只有一行，輸出全部車輛通過小橋的最短時間(minute)，精確到小數點後一位。

Samples

10 5 3
4 10
5 30
5 20

45.0

原始資料

• Zero1 題號：b446
• Hydro 題號：Z1446
• Locale：zh_TW
• Display：practice