Velosiped

Velosipedçi $A$ nöqtəsindən $B$ nöqtəsinə getmək istəyir və bu iki nöqtə arasındakı məsafə $l$ metrdir. Onun $v$ m/s sürətə çata bilən bir velosipedi var. Lakin yola çıxmadan əvvəl, velosipedçi velosipedini bəzi modernizasiyalarla təkmilləşdirə bilər.

Hər bir modernizasiya üçün velosipedin sürətini nə qədər artırdığı və bu modernizasiyanın nə qədər vaxt apardığı məlumdur. Müxtəlif modernizasiyaları həyata keçirmək mümkündür, lakin hər bir modernizasiya yalnız bir dəfə tətbiq oluna bilər. Velosipedçiyə $B$ nöqtəsinə mümkün qədər tez çatmaqda kömək edin.

Giriş məlumatları

Proqram üç tam ədəd oxumalıdır:

nöqtələr arasındakı məsafə $l$, velosipedin başlanğıc sürəti $v$ və müxtəlif modernizasiyaların sayı $N$. Sonra, hər biri müvafiq modernizasiyanı müəyyən edən $N$ cüt tam ədəd gəlir: modernizasiyadan sonra sürət artımı $v_i$ və bu modernizasiyaya sərf olunan vaxt $t_i$. Bütün ölçülər SI sistemində (metr və saniyə) verilir.

$0\le l\le 10^9$, $1\le v\le 10^6$, $0\le N\le 100$, $0\le v_i\le 1000$, $0\le t_i\le 1000$.

Çıxış məlumatları:

Velosipedçinin modernizasiya vaxtını nəzərə alaraq $A$ nöqtəsindən $B$ nöqtəsinə getməsi üçün lazım olan minimum vaxtı altı ondalık dəqiqliklə çıxarın.

Nümunələr