when I was solving this problem, I thought that Igor can go directly to any cell in any row above his current row as long as the Euclidean distance between that cell and his current cell is less than or equal to $$$d$$$

but in the last minutes of the contest, I realized that he can only go to any cell in the row that is exactly above him if he can reach it

with this, I found the solution for the problem faster and I got AC

now, I'm wondering, how to solve this problem if Igor can go to any row as long as he satisfies the constraints ?

for example, in the second testcase, Igor can go from the last row to the first row as mentioned in the image above

the result should be 70

what is the optimal solution for such a problem ?

I'm looking forward to see your ideas and solutions, and thanks ^_^