KNN for Regression

Marlow Energy needs a demand figure for a day whose temperature is forecast but whose gas usage nobody has measured yet. The archive holds past days, each stored as an outdoor temperature and the gas the town actually burned, in no particular order. The forecasters' rule of thumb is to look at the past days whose temperature came closest to the forecast one and report the plain average of what those days burned. Temperature is the only thing compared, and two degrees warmer counts as exactly as close as two degrees colder.

Task: Print the gas usage predicted for the forecast temperature.

Input

The first line holds the forecast temperature followed by k, how many past days to consult, separated by a space. The second line holds n, the number of archived days, at least k. Each of the next n lines holds one archived day's temperature and the gas it burned, separated by a space. Values may be negative or fractional.

Output

One line holding the predicted usage, written with exactly 2 digits after the decimal point. All k consulted days count equally — an exact temperature match gets no more say than the furthest of the k. If days tie on closeness and taking them all would overfill k, keep the ones written earlier.

Example:

Input:
5 2
4
1 10
4 20
6 30
10 40

Output:
25.00