One day, we ACMers of NBUT found the secret between Mr. Cai and TT!
They are hand in hand and decide to have a camping.

They followed the footmark of predecessors - lots of pebbles with order from 1 to N.
The pebbles are too many and TT wants to choose some of them to watch. The pebbles be chosen should be continuous in order.

After they finished watching, Mr. Cai decide to connect some continuous pebbles by a chalk. But because that the chalk is not that long, Mr. Cai must select a solution that cost the minimum chalk.
Can you help Mr. Cai and TT to find a best solution to connect some continuous pebbles with minimum chalk in the pebbles that they had watched?

This problem contains several cases.
The first line of each case is a integer N (2 <= N <= 100, 000), M (2 <= M <= min(10, N), M indicates that the number of pebbles that Mr. Cai should connect after each time they had watched the pebbles) and W (1 <= W <= 100, 000, indicates the times they had watched the pebbles).
Then N lines followed. The ith line contains two number xi and yi (-10, 000 <= xi, yi <= 10, 000), indicates that the coordinate of ith pebbles.
Next follow W lines. Each line contains two integers S and E, means Mr. Cai and TT choose pebble S to pebble E to watch at this time. (E - S >= M)

For each watch, you should tell Mr. Cai the minimum chalk they should cost to connect M continuous pebbles. Six decimal places.
(After each watching and connection, they would erase all the trace)