A desk's daily PnL is iid: each day it takes the value v_i with probability q_i (i = 1..m). Risk asks you to certify an upper bound on the probability that the total PnL over n days reaches at least t.

Certify the best bound available from Markov's inequality applied to the exponential: for every theta > 0,

P(S_n >= t) <= E[e^(theta * S_n)] * e^(-theta * t) = M(theta)^n * e^(-theta * t)

where M(theta) = sum_i q_i * e^(theta * v_i). Output the natural logarithm of the smallest such bound over theta > 0.

Input

The first line contains n, t and m. The next m lines each contain v_i and q_i.

Output

One real number: ln of the optimal bound, with absolute or relative error at most 1e-6.

Constraints

1 <= n <= 10^9

-100 <= v_i <= 100, all distinct, with at most 4 digits after the decimal point

q_i > 0 with at most 6 digits after the decimal point, summing to exactly 1

mean + 0.001 <= t / n <= max(v_i) - 0.001, where mean = sum_i q_i v_i < 0

t has at most 4 digits after the decimal point

Scoring

This is a standard problem: a submission scores full points if it produces the correct output for every test case, and zero otherwise.

Numeric answers are accepted if they are within an absolute tolerance of 1e-06 or a relative tolerance of 1e-06 of the expected value.