As a member of the Special Operations Forces of a small country, your job is to clear a minefield. Unfortunately, military top brass is rather more concerned with politics then the general welfare of their officers. Being in a sad state of ignorance of how mines (and the bodies of soldiers) actually work, they demand you clear the minefield by putting timed ignition charges on each mine.
This does require you to personally fiddle with armed mines of various sizes but invariable deadliness.
Thankfully, you realize in time that when the primary charge of these mines blows up, the shockwave is usually strong enough to blow up other mines in the vicinity - and the other mines blowing up can blow up mines yet farther away. If you could determine which mines to set off to maximize the cascade effect, you could minimize the number of mines you have to manipulate with your own quite defenseless hands.
In short: given a precise map of the minefield, your task is to eliminate all mines by directly setting off as few mines as possible.
N X Y R ... X[N-1] Y[N-1] R[N-1]
Nis the number of mines,
X[i] Y[i]is the coordinates of the ith mine and
R[i]is its detonation radius.
M M ... M[K]K is the minimum number of mine detonations, M[i] is the index of the ith detonated mine.
5 -15 4 10 12 4 8 -10 -4 8 2 10 16 18 10 8