Max Circumference

All submissions for this problem are available.
In the magic land there is a triangle ABC.
You have N spell cards. Each card has two parameters, ith card has parameters x[i] and y[i]. Using of the ith spell card add x[i] to the xcoordinate of the point A and add y[i] to the ycoordinate of the point A. So if A has coordinates (X, Y) it will be moving to (X + x[i], Y + y[i]) by using this card.
You can use at most K spell cards. Applying of several spell cards performs consecutively. So if A was moved to some point A' by the first spell card then second spell card is applied to the new position of A, that is, to the point A', and so on for further cards.
Your task is to find the maximal possible circumference of the triangle ABC after using of at most K spell cards (note that you can use no spell cards). The circumference of a triangle ABC is the sum of its side lengths: AB + BC + CA. And in our problem by triangle we mean any three points A, B, C of the plane. So, in particular, the points A, B, C can lie on the same line, or even some of them can coincide.
Input
The first line of the input contains two integers N and K.
The second line contains two integers Ax and Ay, the coordinates of the point A.
The third line contains two integers Bx and By, the coordinates of the point B.
The fourth line contains two integers Cx and Cy, the coordinates of the point C.
Each of the following N lines contains two integers x[i] and y[i], the parameters of the ith spell card.
Output
Output should contain a single real number rounded to exactly 13 digits after the decimal point, the maximal possible circumference of the triangle ABC that can be achieved by using at most K spell cards. Your answer will be considered as correct if it has an absolute error less than 10^{12}.
Constraints
1 ≤ N ≤ 500
0 ≤ K ≤ N
Ax, Ay, Bx, By, Cx, Cy ≤ 10^{9}
x[i], y[i] ≤ 10^{6}
Example
Input 1: 3 2 0 0 1 0 1 0 0 1 1 0 1 1 Output 1: 6.8284271247462 Input 2: 3 3 0 0 1 0 1 0 0 1 1 0 1 1 Output 2: 7.8416192529638
Explanation:
Case 1. Here the optimal way is to use the 1st and the 3rd spell cards. The new coordinates of the point A will be (1, 2). So the circumference of the new triangle ABC is: (1, 2) − (1, 0) + (1, 0) − (1, 0) + (1, 0) − (1, 2) = 4 + 2 * sqrt(2).
Case 2. Here the optimal way is to use all of the spell cards. The new coordinates of the point A will be (2, 2). So the circumference of the new triangle ABC is: (2, 2) − (1, 0) + (1, 0) − (1, 0) + (1, 0) − (2, 2) = 2 + sqrt(5) + sqrt(13).
Author:  cgy4ever 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/MAXCIR 
Tags  cgy4ever, hard, oct12 
Date Added:  10092012 
Time Limit:  0.37622 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions