Sadiq On a Date

All submissions for this problem are available.
Problem description.
Sadiq had planned to go on a date with his girl friend. He is also a gaming freak so he forgot about his date timings .Now, his girl friend is waiting for him and will be very angry if he doesn’t reach on time. There is timer which shows how much time he has got. As soon as the timer shows 0 , his girlfriend will go back to her hostel and Sadiq will miss his date. Also, there are n clock stations, station number i is located at point (xi,yi) on the plane. As he reaches the station i, he can increase the time on his timer by ai . But the stations are for one time use only, so if he visits some station another time ,the time won’t grow up.
Sadiq spends d.dist time units to move between stations, where dist is the distance the player has covered and d is some constant. The distance between station i and station j is determined as
xixj+yiyj.
Initially, sadiq is at station 1 and he has strictly more than zero and less than one unit time. Though at station 1, one unit of money can increase the time on the timer by one unit time. (Only integer units of time can be bought.)
Now Sadiq needs your help. He wants to know the minimum amount of money he needs to get to station n where his girlfriend is waiting.
Input
Input description.
The first line contains integer n and d (3<=n<=100,1000<=d<=100000) denoting the number of stations and the constant from the statement .
The second line contains n2 integers: a2, a3,… an1 (1<=ai<=1000).
The next n lines contain the coordinates of the stations .The ith line contains two integers xi and yi
(100<=xi,yi<=100).
Output
Output the minimum amount of money in a single line.
Example
Input: 3 1000 1000 0 0 0 1 0 3 Output: 2000
Explanation
Example case 1. He will buy 2000 units of time on station1. He can't move to station 3 directly as it would cost him 3000 units of time which is more than what he has.
So he goes to station 2 which costs him 1000 units of time from staiton1.At station 2 he earns 1000 units of time totalling his time to 3000 units which is sufficient to go from station 2 to station 3.
Author:  varunsekar94 
Tags  varunsekar94 
Date Added:  26012015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 