QQ Farm

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission：31     AC：4     Score：99.62

Description

Many boys and girls play the game QQ farm, For example, in this picture we can see xnby、 Lance and so on. Sometimes there are some mosquitoes in our farm, we use a rectangular-shaped pad to kill them, and our experience will increase by 3 points after killing each mosquito .But now we find that using a square-shaped pad works better. when using the square-shaped pad, if we kill n mosquito at one time, our experience will increase by n×n points. For example, if we kill 4 mosquitoes at one time, our experience will increase by 16 points. A mosquito was killed when it is covered by the pad, but killing them is not so easy, because they are flying all the time. Now we got the radius of the pad and the location of every mosquito in each second, in each second we could use the pad just once, and we must kill at least one mosquito every second. You are asked to write a program to compute how many points we can get at most.

Input

There are multiple test cases.

In each case, The first line contains two integers: N, T, which indicate the number of mosquitoes and the number of seconds.

The second line contains one Real number R, the length of the pad’s side.

The following T lines, each contains N pairs of Real numbers: (X1, Y1), (X2, Y2)…(XT, YT), which indicate the locations of those mosquitoes at the corresponding second.

Those real numbers are rounded to two digits after the decimal point.

The sides of the pad must be parallel to x-axis or Y-axis.

( 0 < N ≤ 10, 0 < T ≤ N, -1000000 ≤ R, Xi, Yi ≤ 1000000 )

Output

The number of points we could get at most.

Samples

input
3 2 2.00 1.00 1.00 2.00 2.00 3.00 3.00 0.00 0.00 2.00 2.00 4.00 4.00 3 1 2.00 1.00 1.00 2.00 2.00 3.00 3.00
output
5 9