You have recently started to feel unsafe in your own house, so you decided to place surveillance radars in the garden. When a radar with range *r* is placed at point *S*, it totally covers the area of the circle with radius *r* centered at point *S*. The maximum allowable range is **R**, and all your radars must be set to the same range.
There are two types of radars - blue and red. You can buy as many of each as you like, but they can only be placed at certain points in the garden. You are given two int[]s **possibleXForBlue** and **possibleYForBlue**, where (**possibleXForBlue**[i], **possibleYForBlue**[i]) is the i-th point where you are allowed to place a blue radar. Similarly, you are given two int[]s **possibleXForRed** and **possibleYForRed** describing the allowable points for red radars. You cannot place more than one radar at a single point. Also, the area covered by blue radars cannot overlap with the area covered by red radars. Otherwise, the whole system will malfunction.
Your goal is to place the radars in such a way that maximizes the safety factor. The safety factor is the sum of all the areas covered by the radars. Note that if an area is covered by multiple radars, it will count multiple times toward the sum. Return the maximal safety factor you can achieve. |