Radio Coverage

A base radio station broadcasts over a circular region centered at $(x_0, y_0)$ with radius $R$.

To enlarge its audience, you may build relay stations at some of $N$ candidate sites. If a relay is built at site $i$, it covers a disk centered at $(x_i, y_i)$ with radius $r_i$. Every candidate site lies inside the base station's region, that is $(x_0 - x_i)^2 + (y_0 - y_i)^2 \le R^2$.

Choose a subset of the sites to build relays so that:

1. no two chosen relay disks overlap each other (they may touch);
2. the total area covered by the base station together with all chosen relays (the area of their union) is as large as possible.

A relay disk may overlap the base station's region; only overlap between two relay disks is forbidden. Report the maximum possible total covered area.

The input contains the integer $N$, then the real numbers $x_0$, $y_0$, $R$, then $N$ triples of real numbers $x_i$, $y_i$, $r_i$. Values are separated by whitespace and may span multiple lines.

Print the maximum total covered area, rounded to $4$ decimal places.

• $1 \le N \le 10$
• $0 \le x_i, y_i, x_0, y_0 \le 1000$
• $1 \le r_i \le R \le 1000$