Jack is a pumpkin that enjoys spooking the citizens of the villages near his pumpkin patch every Halloween. However, every year after someone lights the candle inside of him, he has a limited amount of time to spook everyone before the candle burns out, thus being unable to spook any more villagers because nobody can see him. In past years, he has only been able to spook a small amount of villages due to his poor decision making, but now that he has you to help him, he will be able to spook as many villages as possible!
Given a list of village locations and a candle lifespan, output the maximum number of villages Jack can visit. You do not have to print the path itself.
The lifespan of the candle and a list of village locations in a Cartesian coordinate system. The pumpkin patch Jack originates from will always be at 0,0. You may format the input in anyway you wish. To simplify Jack's movements, he can only move horizontally, vertically, or diagonally, meaning his candle will either lose 1 or 1.5 (he takes a bit longer diagonally) units of life every move. The candle burns out when the lifespan is less than or equal to 0.
An integer equal to the maximum number of villages Jack can visit before the candle burns out.
This is code-golf, so shortest code in bytes wins. Standard loopholes are not allowed.
// Format [lifespan] [list of village coordinates] -> [maximum visit-able villages] 4 -1,0 1,0 2,0 3,0 4,0 5,0 -> 3 4 1,1 2,2 3,3 -> 2 5 1,1 2,1 3,1 4,1 5,0 5,1 -> 4